[c++] BOJ 1013 :: Contact

문제

[Contact 문제 바로가기]

전파의 기본 단위는 { 0 , 1 } 두 가지로 구성되어있으며, x+ (  ) 는 임의의 개수(최소 1개) x의 반복으로 이루어진 전파의 집합을 나타낸다.반복을 의미하는 + 외에도 or 를 의미하는 | 기호가 있다. { x | y } 는 x 혹은 y 를 의미하는 것으로, { 0+ | 1+ } 는 { 0 , 1 , 00 , 11 , 000 , 111 , … } 의 집합을 의미한다. 아래는 두 기호를 복합적으로 사용한 예이다.

• (100+1+ | 01)+

김동혁 박사는 다양한 전파 기록 중에서 위의 패턴을 지니는 전파를 가려내는 프로그램을 필요로 한다. 이를 수행할 수 있는 프로그램을 작성하라.

 

풀이

패턴이 정해져있고 각 패턴의 시작 문자가 다르기 때문에, 각각의 패턴에 해당하는 지를 판별하는 함수를 하나 사용하면 된다. 하지만 다양한 패턴으로 해석될 수 있는 경우가 있는데, 다음과 같은 경우이다.

011000111001

처음 풀었을 때 "01", "100,,,1,,," 패턴을 조사하면서 후자의 패턴에서 1 이후에 오는 0을 찾는 식으로 풀이를 구성하였다. 그렇게 하니 위의 패턴은 "01 1000111 001"로 해석될 수 있는데 이후에 나오는 001이 아무 패턴과도 일치하지 않으므로 NO를 출력하게 되어버렸다. 하지만 해당 패턴은 "01 100011 1001"으로 "YES"를 출력해야 하는 예제이다. 따라서 100+1+ 패턴에서 1의 개수에 따라 모든 경우의 수를 체크하는 방식으로 변경하였고, 그러기 위해서 재귀로 함수를 구성하였다.

 

코드

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

int findPattern(string str){ // 0:YES, 1:NO
	if(str.length() == 0) return 0;
	if(str[0] == '0'){ // 01 패턴
		if(str.length() >= 2 && str[1] == '1'){
			str = str.substr(2);
			return findPattern(str); // 패턴 제거 후 재귀
		}
		return 1;
	}else{ // 100+1+ 패턴
		if(str.length() >= 4 && str.substr(0, 3) == "100"){
			str = str.substr(3); // 100 제거
			int startIdx = str.find('1');
			if(startIdx == string::npos){ // 1이 없으면 실패
				return 1;
			}
            
			str = str.substr(startIdx); // 1 이전의 문자들 제거
			while(str.length() >= 1 && str[0] == '1'){
            	// 문자를 하나씩 제거해가며 성공하는 경우가 나올 때까지 체크
				str = str.substr(1);
				if(findPattern(str) == 1){
					continue;
				}
				return 0; // 성공
			}
			return findPattern(str); // 패턴 제거 후 재귀
		}
		return 1;
	}
}

int main() {
	int T; cin >> T;
	while(T--){
		string str; cin >> str;
        
		if(findPattern(str) == 1) cout << "NO" << '\n';
		else cout << "YES" << '\n';
	}
}

 

결과

 

증말 숏코딩 못하는 나 ㅎ...