개발 블로그

문제 링크 : https://www.acmicpc.net/problem/5052

문제

전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오.

전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다.

예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자

• 긴급전화: 911
• 상근: 97 625 999
• 선영: 91 12 54 26

이 경우에 선영이에게 전화를 걸 수 있는 방법이 없다. 전화기를 들고 선영이 번호의 처음 세 자리를 누르는 순간 바로 긴급전화가 걸리기 때문이다. 따라서, 이 목록은 일관성이 없는 목록이다.

입력

첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 하나씩 주어진다. 전화번호의 길이는 길어야 10자리이며, 목록에 있는 두 전화번호가 같은 경우는 없다.

출력

각 테스트 케이스에 대해서, 일관성 있는 목록인 경우에는 YES, 아닌 경우에는 NO를 출력한다.

접근 방법

처음에는 3중 포문을 돌면서 현재 문자열에 대해 n-1개의 전화번호를 다 돌면서 비교하는 완전탐색을 했는데 시간초과가 났다.

그러나 아래의 경우를 생각해보면 문자열을 sort() 한 뒤, 현재 문자열을 기준으로 삼고 현재 문자열이 바로 다음 문자열의 접두어가 되는지만 판단하면 시간 안에 해결할 수 있다. 

123

1234

134

=> NO

123

1245

13

=> YES

이때, 현재 문자열의 길이가 다음 문자열의 길이보다 길면 접두어가 될 수 없으므로 스킵하면 더욱 시간을 단축할 수 있다.

//
//  문자열_BOJ5052_전화번호목록.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/07/07.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    int t; cin >> t;
    for(int test_case = 1; test_case<=t; test_case++){
        int n; cin >> n;
        string str;
        vector<string> vecStr;
        for(int i = 0; i<n; i++){
            cin >> str;
            vecStr.push_back(str);
        }
        sort(vecStr.begin(), vecStr.end());
        bool flag = true;
        for(int i = 0; i<vecStr.size()-1; i++){
            
            string cur = vecStr[i];
            string next = vecStr[i+1];
            flag = true;
            if(cur.length() > next.length()) continue;
            if(cur == next.substr(0, cur.length())){
                flag = false;
                break;
            }
        }
        if(!flag) cout << "NO\n";
        else cout << "YES\n";
    }

    return 0;
}

문제 링크 : https://www.acmicpc.net/problem/2745

문제

B진법 수 N이 주어진다. 이 수를 10진법으로 바꿔 출력하는 프로그램을 작성하시오.

10진법을 넘어가는 진법은 숫자로 표시할 수 없는 자리가 있다. 이런 경우에는 다음과 같이 알파벳 대문자를 사용한다.

A: 10, B: 11, ..., F: 15, ..., Y: 34, Z: 35

입력

첫째 줄에 N과 B가 주어진다. (2 ≤ B ≤ 36)

B진법 수 N을 10진법으로 바꾸면, 항상 10억보다 작거나 같다.

출력

첫째 줄에 B진법 수 N을 10진법으로 출력한다.

접근 방법

입력한 문자열 N을 한글자씩 따라가면서 10진수로 변환해나간다.

해당 char 이 '0' ~ '9'인 경우와 'A'~'Z'인 경우로 나눠서 계산한다. 

//
//  문자열_BOJ2745_진법변환.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/07/07.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

#include <iostream>
#include <cmath>
using namespace std;

int main(){
    
    string N;
    int B;
    cin >> N >> B;
    
    int len = (int)N.length();
    int bit = len-1;
    
    int ans = 0;
    
    for(int i = 0; i<len; i++){
        
        char c = N[i];
        int num = 0;
        
        if(65<=c && c<=90) num = c - 55;    //'A' ~ 'Z'
        else num = c - '0';//'0' ~ '9'
        
        ans += num * pow(B, bit-i);
        
    }
    cout << ans;
\
    return 0;
}

문제 링크 : https://www.acmicpc.net/problem/1373

문제

2진수가 주어졌을 때, 8진수로 변환하는 프로그램을 작성하시오.

입력

첫째 줄에 2진수가 주어진다. 주어지는 수의 길이는 1,000,000을 넘지 않는다.

출력

첫째 줄에 주어진 수를 8진수로 변환하여 출력한다.

접근 방법

세자리씩 끊어서 8진수로 변환해야 하므로, 길이를 3의 배수로 맞춰준다.

str = "011001100"을 세자리씩 끊어서 생각해보자.

011 = 0*4 + 1*2 + 1*1 = 3

001 = 0*4 + 0*2 + 1*1 = 1

100 = 1*4 + 0*2 + 0*1 = 4

인 것을 확인할 수 있다. 

(16진수는 4자리씩 끊어서 생각하면 된다.)

//
//  문자열_BOJ1373_2진수8진수.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/07/07.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

#include <iostream>
#include <cmath>
using namespace std;

int main(){ cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
    
    string str; cin >> str;
    while(str.length() % 3 != 0){
        str = '0' + str;
    }

    for(int i = 0; i<str.length(); i+=3){   //i = 0, 3, 6, ,,
        int num = (str[i]-'0')* 4 + (str[i+1]-'0')* 2 + (str[i+2] - '0')* 1;
        cout << num;
    }
       
    return 0;
}

문제 링크 : https://www.acmicpc.net/problem/1062

문제

남극에 사는 김지민 선생님은 학생들이 되도록이면 많은 단어를 읽을 수 있도록 하려고 한다. 그러나 지구온난화로 인해 얼음이 녹아서 곧 학교가 무너지기 때문에, 김지민은 K개의 글자를 가르칠 시간 밖에 없다. 김지민이 가르치고 난 후에는, 학생들은 그 K개의 글자로만 이루어진 단어만을 읽을 수 있다. 김지민은 어떤 K개의 글자를 가르쳐야 학생들이 읽을 수 있는 단어의 개수가 최대가 되는지 고민에 빠졌다.

남극언어의 모든 단어는 "anta"로 시작되고, "tica"로 끝난다. 남극언어에 단어는 N개 밖에 없다고 가정한다. 학생들이 읽을 수 있는 단어의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문자로만 이루어져 있고, 길이가 8보다 크거나 같고, 15보다 작거나 같다. 모든 단어는 중복되지 않는다.

출력

첫째 줄에 김지민이 K개의 글자를 가르칠 때, 학생들이 읽을 수 있는 단어 개수의 최댓값을 출력한다.

접근 방법

int형은 4byte( = 32bit) 이므로 0부터 (2^32 - 1)까지 표현할 수 있다. 

여기서 알파벳은 총 26개이므로 0번비트부터 25번 비트까지만 사용하므로 int 형 내에서 커버가능하다.

먼저 N개의 단어를 입력받는데, 이때 단어를 이루고 있는 알파벳을 체크해서 word[]에 비트마스크로 표시한다. 

ex) 0번째 단어가 "antarctica"라고 하면, 이 단어를 이루고 있는 알파벳 [a,c,i,n,r,t]를 아래와 같이 비트로 표현해서 word[0]에 저장한다.

그 다음으로 K의 값을 따진다.

case 1) 5보다 작으면 N개 단어 모두 읽지 못하게 될 것이다. 왜냐하면 N개의 단어들 중에 최대한 많이 읽어야 하는데, 각 단어는 무조건 "a,n,t,i,c"가 포함된다고 했기 때문이다.

case 2) 만약 K가 26이면 모든 알파벳을 알고 있으므로 N개의 단어 모두 읽을 수 있다.

case 3) K가 5도 아니고 26도 아니면 chcked 변수를 초기화한뒤 DFS()를 호출한다.

cheked 변수는 이때까지 배운 알파벳들을 비트로 표현한 것이다.

DFS()에서는 완전탐색으로 26개의 알파벳 중에 K-5개를 선택하는 모든 경우를 따지게 된다. 단, 시간복잡도를 줄이기 위해 start 파라미터를 이용해서 중복조합을 구했다. (a,b를 선택하는 경우나 b,a를 선택하는 경우나 같기 때문이다.)

toPick이 0이 되면, 즉 배워야할 알파벳을 다 선택했으면, 그 알파벳들로 읽을 수 있는 단어가 N개 중 몇개인지 카운트한다. 

알파벳을 선택하는 조합을 바꿀 때마다 "읽을 수 있는 단어 수의 최대값"을 갱신한다. 

모든 경우를 따진 뒤 최대값을 출력한다.

//
//  비트_BOJ1062_가르침.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/07/07.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int checked;
int word[50];   //N 최대 50개
int N, K;

int maxi = 0;

void DFS(int toPick, int start, int checked){    //증복조합
    
    if(toPick==0){  //배울 알파벳 골랐으면
        
        //그 알파벳들로 N개 단어 중 몇개 읽을 수 있는지 카운트해서 최대값 찾기
        int cnt = 0;
        for(int i = 0; i<N ;i++){
            if((word[i] & checked) == word[i]) cnt++;
        }
        if(maxi < cnt) maxi = cnt;
        return;
    }

    for(int i = start; i<26; i++){
        if((checked & (1<<i)) == 0){   //방문 안 한 경우에만
            checked |= (1<<i);
            DFS(toPick-1, i, checked);
            checked &= ~(1<<i);
        }
        
    }
}

int main(){
    
    cin >> N >> K;
    
    string str;
    for(int i = 0; i<N; i++){
        cin >> str;
        
        int num = 0;
        for(int j = 0; j<str.length(); j++){
            num |= 1 << (str[j] - 'a');
        }
        word[i] = num;
    }
    
    if(K<5) cout << 0;  //anta ~ tica 읽으려면 최소 a,n,t,i,c 5개 이상은 알고 있어야함
    else if (K==26) cout << N;
    else{
        
        //a, n, t, i, c 를 이미 알고 있음을 초기화.
        checked |= 1 << ('a'-'a');
        checked |= 1 << ('n'-'a');
        checked |= 1 << ('t'-'a');
        checked |= 1 << ('i'-'a');
        checked |= 1 << ('c'-'a');
        
        DFS(K-5, 0, checked);
        cout << maxi;
    }
 
    return 0;
}

문제 링크 : https://www.acmicpc.net/problem/2098

문제

외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자.

1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 이런 여행 경로는 여러 가지가 있을 수 있는데, 가장 적은 비용을 들이는 여행 계획을 세우고자 한다.

각 도시간에 이동하는데 드는 비용은 행렬 W[i][j]형태로 주어진다. W[i][j]는 도시 i에서 도시 j로 가기 위한 비용을 나타낸다. 비용은 대칭적이지 않다. 즉, W[i][j] 는 W[j][i]와 다를 수 있다. 모든 도시간의 비용은 양의 정수이다. W[i][i]는 항상 0이다. 경우에 따라서 도시 i에서 도시 j로 갈 수 없는 경우도 있으며 이럴 경우 W[i][j]=0이라고 하자.

N과 비용 행렬이 주어졌을 때, 가장 적은 비용을 들이는 외판원의 순회 여행 경로를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다.

항상 순회할 수 있는 경우만 입력으로 주어진다.

출력

첫째 줄에 외판원의 순회에 필요한 최소 비용을 출력한다.

접근 방법

처음에는 DFS로 완전탐색을 생각했었는데,

1->2->3->4->1

2->3->4->1->2

이와 같이 중복이 발생하므로 DP와 비트연산을 사용했다.

먼저 아래와 같이 정의한다. 

- W : 그래프 G = (V,E)의 인접 행렬 (노드의 연결 관계 나타냄)

- V : 모든 도시의 집합

- A : V의 부분 집합

- D[Vi][A] : A에 속한 도시를 한 번씩만 방문해서 Vi -> V1(시작 노드)로 가는 최단 경로의 길이

여기서 우리가 구할 것은 A가 시작노드인 V1만 제외한 부분집합일 때 즉,  D[Vi][A-{V1}]을 구하는 것이다. 

이제 재귀 관계식을 구하면 아래와 같다. 

- A가 공집합이라면, D[Vi][공집합]은 아무것도 거치지 않고 다이렉트로 Vi -> V1으로 가는 경우이다. 이것은 인접행렬로부터 값을 바로 얻을 수 있다.

- A가 공집합이 아니라면, D[Vi][A]는 두 파트로 나뉜다.

1) W[i][j] : 처음 시작 노드 Vi에서 Vj로 가는 거리(다이렉트 거리)

2) D[Vj][A-{Vj}] : Vj에서 시작해서 {Vi, Vj를 제외한 모든 노드}를 방문하고 다시 시작 노드 Vi로 가는 경로의 길이

예를 들어, j = 2이면 A - {Vj} = {V3, V4}이고, 시작노드 Vi를 V1이라고 하자.

그럼 D[v1][{V3, V4}] = min(W[1][2] + D[V2][{V3, V4}]) = min(length(V1,V2,   V3,V4,V1) , length(V1,V2,    V4,V3,V1))이다.

자세한 설명은 주석으로 표시했다. 

//
//  비트_BOJ2098_외판원순회.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/07/06.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;

#define INF 987654321
#define MAX 16
int N;
int W[MAX][MAX];
int dpCost[MAX][1<<MAX];   //1<<16 = 2^16개의 노드의 방문 여부를 비트로 표시.
int allVisitBit;

int DFStravel(int cur_node, int visited_bit){   //cur_node : 현재 위치 , visited_bit : 현재 위치를 포함해서 방문했던 곳들 비트로 표현
    
    if(visited_bit == allVisitBit){             //다 돌았는데
        if(W[cur_node][0]==0) return INF;   //현재 위치에서 첫 시작 노드(0번)로 돌아갈 수 없으면
        else return W[cur_node][0];         //다 돌고 첫 시작노드로 돌아갈 수 있으면??
    }
    
    //-1이 아니라면 자명한 최소값(dpCost[][]) 바로 리턴.
    if(dpCost[cur_node][visited_bit] != -1 ) return dpCost[cur_node][visited_bit];
    
    //-1이라면
    dpCost[cur_node][visited_bit] = INF;
    for(int i = 0; i<N; i++){
        
        if(W[cur_node][i] == 0) continue;   //연결 안 되어 있어서 길이 없거나
        if((visited_bit) & (1<<i)) continue;    //이미 방문한 곳이면
        
        //DFStravel(i, visited_bit|1<<i) : 현재 노드에서 재귀적으로 다음 노드 방문.
        dpCost[cur_node][visited_bit] = min(dpCost[cur_node][visited_bit],
                                            W[cur_node][i] + DFStravel(i, visited_bit|1<<i));
    }
    return dpCost[cur_node][visited_bit];
}



int main(){
    
    cin >> N;
    
    for(int i = 0; i<N; i++){
        for(int j = 0; j<N; j++){
            cin >> W[i][j];
        }
    }
    
    allVisitBit = (1<<N) - 1;       //N개 노드 모두 다 방문한 경우 (111...11)
    memset(dpCost, -1, sizeof(dpCost));
    
    int ans = DFStravel(0,1); //0 : 0번 노드가 첫 시작노드 / 1 : 1은 2^0 -> 즉 시작 노드인 0번 노드를 방문했음을 표시)
    //어떤 도시에서 출발하던 비용은 같으므로 0번 노드를 첫 시작노드로 임의 설정.
    
    cout << ans;
    
    return 0;
}

참고 : (https://yabmoons.tistory.com/358),(https://www.youtube.com/watch?v=wj44Dd0zdzM)

문제 링크 : https://www.acmicpc.net/problem/1094

문제

지민이는 길이가 64cm인 막대를 가지고 있다. 어느 날, 그는 길이가 Xcm인 막대가 가지고 싶어졌다. 지민이는 원래 가지고 있던 막대를 더 작은 막대로 자른다음에, 풀로 붙여서 길이가 Xcm인 막대를 만들려고 한다.

막대를 자르는 가장 쉬운 방법은 절반으로 자르는 것이다. 지민이는 아래와 같은 과정을 거쳐서 막대를 자르려고 한다.

1. 지민이가 가지고 있는 막대의 길이를 모두 더한다. 처음에는 64cm 막대 하나만 가지고 있다. 이때, 합이 X보다 크다면, 아래와 같은 과정을 반복한다.
   1. 가지고 있는 막대 중 길이가 가장 짧은 것을 절반으로 자른다.
   2. 만약, 위에서 자른 막대의 절반 중 하나를 버리고 남아있는 막대의 길이의 합이 X보다 크거나 같다면, 위에서 자른 막대의 절반 중 하나를 버린다.
2. 이제, 남아있는 모든 막대를 풀로 붙여서 Xcm를 만든다.

X가 주어졌을 때, 위의 과정을 거친다면, 몇 개의 막대를 풀로 붙여서 Xcm를 만들 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 X가 주어진다. X는 64보다 작거나 같은 자연수이다.

접근 방법

가장 먼저 생각나는 방법은 우선순위 큐를 이용해 막대기 길이를 오름차순 정렬해서 구현하는 것이었다.

@ 우선순위 큐는 디폴트가 내림차순 정렬이므로, 오름차순 정렬을 위해서는 아래와 같이 선언해주어야 한다. 

priority_queue<int, vector<int>, greater<int>> pq;

그러나 문제를 잘 생각해 보면 처음 가지고 있는 막대기 길이는 64(=2^6)으로 항상 같고,

막대기를 항상 절반으로 자르기 때문에 비트마스킹을 활용해서 풀 수도 있다.

즉, X를 이진수로 나타냈을 때의 1의 개수가 답이 되는 것이다. 처음에 이해가 잘 되지 않았지만 입력 예제를 활용해서 한 단계씩 따져보면 금방 파악할 수 있다.

(백준 사이트 기준으로 두 코드 모두 실행시간은 0ms이다.)

//
//  SM_BOJ1094_막대기.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/07/06.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

#include <iostream>
#include <queue>
using namespace std;

int main(){
    
    int X; cin >> X;
    
    priority_queue<int, vector<int>, greater<int>> pq;
    pq.push(64);
    int sum = 64;
    
    while(sum>X){

        //1. 제일 짧은 막대기 꺼내서 절반으로 나누기
        int half = pq.top() / 2;
        pq.pop();
        
        //2. 절반으로 나눈 막대기 2개 push
        pq.push(half);
        pq.push(half);
        
        //3. 제일 짧은 막대기의 절반을 뺀 수가 X보다 크거나 같다면 버림.
        if(sum - half >= X){
            int mini = pq.top();
            sum -= mini;
            pq.pop();
        }
    }
    cout << pq.size();
    return 0;
}

#include <iostream>
using namespace std;

int main(){
    
    int X; cin >> X;
    int ans = 0;
    for(int i = 0; i<=6; i++){
        if(X & (1<<i)) ans += 1;
    }
    cout << ans;
    return 0;
}

문제 링크  : https://www.acmicpc.net/problem/2671

문제

일반적으로 잠수함 엔진이 작동할 때에 나오는 소리는 잠수함의 종류에 따라서 다르다고 한다.

우리는 물속에서 들리는 소리의 패턴을 듣고서 그 소리가 특정한 잠수함에서 나오는 소리인지 아닌지를 알아내려고 한다. 이 문제에서는 잠수함의 소리가 두 종류의 단위 소리의 연속으로 이루어져 있고, 그 단위 소리를 각각 0과 1로 표시한다.

또, 한 특정한 소리의 반복은 ~로 표시한다. 예를 들어 x~는 x가 한번 이상 반복되는 모든 소리의 집합을 말하고, (xyz)~는 괄호 안에 있는 xyz로 표현된 소리가 한번 이상 반복되는 모든 소리의 집합을 말한다. 다음의 예를 보라.

• 1~ = {1, 11, 111, 1111, ..., 1...1, ...}
• (01)~ = {01, 0101, 010101, 01010101. ...}
• (1001)~ = {1001, 10011001, ..., 100110011001...1001, ...}
• 10~11 = {1011, 10011, 100011, ..., 1000...011, ...}
• (10~1)~ = {101, 1001, 10001, 100001, ...1011001, ...100110110001101, ...}

​그리고 (x|y)는 x또는 y중에서 아무거나 하나만을 선택해서 만든 소리의 집합, 즉 집합{x, y}를 의미한다. 예를 들면(1001|0101)은 집합으로 {1001, 0101}을 의미한다. 따라서 (0|1)~은 0과 1로 이루어진 모든 스트링의 집합, 즉 모든 소리의 집합을 말한다. 또 한 예를 보면 (100|11)~은 100과 11을 마음대로 섞어서 만들 수 있는 모든 소리의 집합을 의미한다. 즉 (100|11)~에 해당하는 스트링을 집합으로 나타내면 {100, 11, 10011, 100100100, 1110011, ...}이 된다. 우리가 식별하고자 하는 잠수함의 엔진소리의 패턴은 다음과 같다.

(100~1~|01)~

여기에 속하는 소리의 예를 들어보면, 1001, 01, 100001, 010101, 1000001110101, 1001110101, 0101010101, 10010110000001111101, 01010101011000111, 10000111001111, ...이다.

다시 말해서 이것은 100~1~과 01을 임의로 섞어서 만들 수 있는 모든 스트링의 집합을 나타낸다.

입력으로 0과 1로 구성된 스트링이 주어질 때, 이 스트링이 앞에서 기술된 잠수함의 엔진소리인지 아닌지를 판별하는 프로그램을 작성하라.

접근 방법

주어진 식은 (100~1~|01)~ 이다.

- part A : 100~

- part B : 1~

 - part C = 01

이라고 하자. 

그 후, next State = cur State + next Char 형식에 맞춰서 나올 수 있는 모든 경우를 계산해보면 다음과 같다.

이렇게 구한 값은 unordered_map<string, vector<string>> umap에 넣어주면 된다.

이때 주의할 점은 value에 해당하는 vector에 nextState값을 넣을 때 인덱스를 고려해서 넣어야한다. 즉, next Char 이 0이면 vector의 0번째 인덱스 [0]에 넣어주고, 1이면 1번째 인덱스[1]에 넣어준다. 그래야 입력된 문자열을 한 글자씩 따라가면서 주어진 형식을 어긋나지 않는지 검사할 수 있다.

그렇게 입력된 문자열을 다 검사한 뒤에, state의 값을 검사한다. 이때 잠수함 엔진소리라면 

case 1) part A -> part B에서 끝나거나

case 2) part C 에서 끝나야 한다. 

case 1)은 "100~1" 와 "100~1~"이 해당되고, case 2)는 "01"이 해당된다.

마지막 state 값이 이 세가지 중 하나라면 잠수함 엔진소리가 맞고, 그 외는 엔진소리가 아니다.

//
//  BF_BOJ2671_잠수함식별.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/07/06.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//


#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;

int main(){
    
    string str;
    cin >> str;
    
    unordered_map<string, vector<string>> umap;
    
    umap["init"] = {"0","1"};
    umap["0"] = {"X", "01"};
    umap["1"] = {"10", "X"};
    umap["01"] = {"0", "1"};
    umap["10"] = {"100", "X"};
    umap["100"] = {"100~", "100~1"};
    umap["100~"] = {"100~", "100~1"};
    umap["100~1"] = {"0", "100~1~"};
    umap["100~1~"] = {"10 or 0", "100~1~"};
    umap["10 or 0"] = {"100", "01"};
    
    string state = "init";
    for(int i = 0; i<str.length(); i++){
        int nextChar = str[i] - '0';
        state = umap[state][nextChar];
        if(state == "X") break;
    }
    
    if(state == "100~1" || state == "100~1~" || state =="01") cout << "SUBMARINE";
    else cout << "NOISE";
    
    
    
    return 0;
}

(사실 <regex> 라이브러리를 활용하면 한 줄로 끝난다.)

참고  : (https://gglifer-cs.tistory.com/74)

문제 링크 : https://www.acmicpc.net/problem/1032

문제

시작 -> 실행 -> cmd를 쳐보자. 검정 화면이 눈에 보인다. 여기서 dir이라고 치면 그 디렉토리에 있는 서브디렉토리와 파일이 모두 나온다. 이때 원하는 파일을 찾으려면 다음과 같이 하면 된다.

dir *.exe라고 치면 확장자가 exe인 파일이 다 나온다. "dir 패턴"과 같이 치면 그 패턴에 맞는 파일만 검색 결과로 나온다. 예를 들어, dir a?b.exe라고 검색하면 파일명의 첫 번째 글자가 a이고, 세 번째 글자가 b이고, 확장자가 exe인 것이 모두 나온다. 이때 두 번째 문자는 아무거나 나와도 된다. 예를 들어, acb.exe, aab.exe, apb.exe가 나온다.

이 문제는 검색 결과가 먼저 주어졌을 때, 패턴으로 뭘 쳐야 그 결과가 나오는지를 출력하는 문제이다. 패턴에는 알파벳과 "." 그리고 "?"만 넣을 수 있다. 가능하면 ?을 적게 써야 한다. 그 디렉토리에는 검색 결과에 나온 파일만 있다고 가정하고, 파일 이름의 길이는 모두 같다.

입력

첫째 줄에 파일 이름의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에는 파일 이름이 주어진다. N은 50보다 작거나 같은 자연수이고 파일 이름의 길이는 모두 같고 길이는 최대 50이다. 파일이름은 알파벳과 "." 그리고 "?"로만 이루어져 있다.

출력

첫째 줄에 패턴을 출력하면 된다.

접근 방법

//
//  문자열_BOJ1032_명령프롬프트.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/07/04.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

#include <iostream>
#include <string>
#include <string.h>
using namespace std;

int main(){
    
    int N; cin >> N;
    string str="";
    
    char arr[50];
    
    cin >> str;
    
    for(int i = 0; i<str.length(); i++)  arr[i] = str[i];
    
    for(int i = 1; i<N; i++){
        cin >> str;
        for(int s = 0; s<str.length(); s++){
            if(arr[s] != str[s]) arr[s] = '?';
        }
    }
    for(int i = 0; i<str.length(); i++) cout << arr[i];
    return 0;
}