Contact( BOJ 1013 )

문제 : https://www.acmicpc.net/problem/1013

1013번: Contact

 

문제 파악하기

주어진 N개의 문자열이 각각 (100+1+ | 01)+ 을 만족하는지 확인하는 문제입니다. 라이브러리 함수를 사용하거나 오토마타를 사용하는 방법도 있지만, 여기에서는 반복문과 문자열만을 사용하여 문제를 해결해보겠습니다.

 

문제 해결하기

문자열을 탐색할 때에는 현재 어떤 문자열 형식을 확인하고 있는지 파악하는 것이 중요합니다. 우리는 "100+1+" 형식과 "01" 형식 중 하나를 만족해야 하며, 만약 확인하는 도중 문자 1개라도 틀린 경우에는 "NO"를 출력해야 합니다. 그럼 어떤 형식을 만족하고 있는지 확인할 수 있는 탐색의 시작 경우에는 무엇이 있을까요?

 

가장 먼저 떠오르는 경우는 현재 확인하고 있는 형식의 인덱스 값이 끝까지 이동한 경우입니다. 이 경우에는 새롭게 확인할 형식을 선택해야 하며, 이 때 맨 앞에 위치한 숫자 0과 1로 구분할 수 있습니다. 그리고 놓치기 쉬운 경우의 수는 바로 다음 문자열이 "100"인 경우입니다. 물론 여기에는 조건이 한 가지 더해집니다. 바로 "100+1+" 형식을 확인하는 중 맨 마지막 '+'를 확인하고 있다는 조건입니다. 만약 현재 확인할 문자열부터 다음에 나올 문자열이 100이라면 새롭게 "100+1+"문자열을 확인해야 합니다. 단순히 1이 나왔기에 '+'에 맞게 확인하면 절대 정답을 구할 수 없기 때문입니다.

 

이렇게 탐색을 새롭게 시작하는 2가지 경우를 살펴보았습니다. 2가지 경우를 토대로 탐색을 시작하되, 서로 일치하지 않은 문자가 나온 경우에는 바로 탐색을 종료하고 "NO"를 출력하면 됩니다. 또한, 탐색이 무사히 끝났다고 무조건 "YES"를 출력하면 안 됩니다. 탐색이 끝난 이후에는 지금까지 확인했던 문자열 형식을 모두 확인하였는지 검토한 후에 "YES"를 출력하면 됩니다. 자세한 소스코드는 다음과 같습니다.

 

소스코드

#include <iostream>
#include <string>
using namespace std;
 
int T;
string str;
 
int sw, f;
char temp;
 
int idx[2];
string check[2] = {"01", "100+1+"};
 
int main() {
    cin >> T;
    while(T--) {
        // input
        cin >> str;
        
        f = 1;
        idx[0] = idx[1] = 0;
        
        for(int i=0;i<str.length() and f;) {
            // 초기 설정
            if(idx[0] == idx[1]) sw = str[i]-'0';
            
            // 파싱
            if(check[sw][idx[sw]] == '+') {
                temp = check[sw][idx[sw]-1];
                
                if(temp != str[i]) idx[sw]++;
                else {
                    // 특수 케이스 >> 100인 경우
                    if(i+4>str.length()) i++;
                    else {
                        string s;
                        for(int j=0;j<3;j++) s.push_back(str[i+j]);
                        
                        if(s == "100") idx[sw]++;
                        else i++;
                    }
                }
            }
            else {
                temp = check[sw][idx[sw]];
                
                if(temp != str[i]) f = 0;
                else {
                    idx[sw]++;
                    i++;
                }
            }
            
            // 초기화
            if(idx[sw] == check[sw].length()) idx[sw] = 0;
        }
        
        // print
        if( (idx[0] == idx[1] or idx[1] >= 5 ) and f ) cout << "YES\n";
        else cout << "NO\n";
    }
}
/*
1
100000110
ans: NO
*/
 

후기

잠수함 식별(KOI 1999) 기출 문제와 거의 흡사한 문제입니다. 단순히 정규 표현식 라이브러리(std::regex)를 사용하여 문제를 해결할 수 있지만 직접 경우의 수를 나눠보면서 문제를 풀어보면 알고리즘을 철저하게 세우는 연습을 할 수 있다고 생각합니다. 추후에는 오토마타를 이용하여 문제를 해결하는 방법도 공부해야 겠다는 생각이 드네요.