(BOJ) 잠수함 식별_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로 구성된 스트링이 주어질 때, 이 스트링이 앞에서 기술된 잠수함의 엔진소리인지 아닌지를 판별하는 프로그램을 작성하라.

입력

0과 1로 구성된 스트링이 1개 들어있다. 이때 각 스트링의 길이는 150개 이하로 제한된다.

출력

입력에 들어있는 스트링을 읽고, 이것이 잠수함의 엔진소리를 나타내는 스트링인지 아니면 그냥 물속의 잡음인지를 판정한 후, 잠수함의 엔진 소리에 해당하는 스트링이면 "SUBMARINE"을 출력하고, 그렇지 않으면 "NOISE"를 출력한다.

풀이 1

사실, 오토마타를 공부하고 싶고 관련 문제를 찾아보다가 발견한 문제인데, 처음 문제를 보았을 때 오토마타보다는 문자열 처리하는 방법이 더욱 떠올랐다.

문제를 보면, (100~1~|01)~에서 100~1~(파트1)과 01(파트2)으로 나뉘게 되고 주어진 문자열에 대해서 1로 시작하는지 0으로 시작하는지부터 따지면 될 것 같았다. 또한, 한 파트에 대해서 비교가 끝나고 조건을 만족하면 그 다음 문자가 1로시작하는지 0으로 시작하는지 따지고 결정된 한 파트에 대해서 비교해보는 작업을 반복하면 된다.

1로 시작하는 경우

1. 부분 문자열 시작지점부터 두 칸 뒷부분까지 비교해서 "100"이 아닐 경우 NOISE

2. 문자열에서 1이 나올 때까지 pass하기

3. 1~이라고 냅다 0이 나올 때까지 pass하면 안된다. 뒤에 나오는 부분문자열을 따져봐야 한다.

• 뒤에 나오는 부분문자열이 "100"인 경우
  10011001 처럼 (파트1)이 연속으로 두 번 나올 수 있다.
  
  현재 10011001인 상태(빨간색으로 표시된 부분까지는 확인된 상태이고 파란색으로 표시된 부분에 멈춰있는 상태)인데 인덱스 5번째 문자가 1이라고 그냥 패스해버리면 그 다음에 연속으로 0이 두 번 나오게 되어 NOISE라고 출력할 것이다.
  
  하지만, 1001 1001 과 같이 쓸 수 있으므로 이 문자열의 답은 SUBMARINE이다.
  
  
  
• 2) 뒤에 나오는 부분문자열이 "01"인 경우
  파트1 문자열과의 비교를 마치게 된다. 그리고 뒤에 나올 부분문자열이 파트2에 해당하는 것을 암시한다.

0으로 시작하는 경우

1. 부분문자열이 "01"인지 아닌지 비교하고 일치하지 않는 경우 NOISE

위와 같은 과정을 거칠 때 뒤에 남아있는 문자열 길이도 잘 봐야한다. 문자열 길이 이상의 인덱스에 접근하게 되면 터질테니 말이다. 코드로 옮기면 다음과 같다.

#include <iostream>
#include <string>
#include <stdlib.h>

using namespace std;

int main() {
	string input;
	cin >> input;
	int size = input.size();
	int i = 0;

	while (i < size) {
		if (input[i] == '1') {
			if (i + 2 < size && input.substr(i, 3) == "100") {
				i = i + 3;
				while (input[i] == '0') {
					i++;
				}
			}
			else {
				cout << "NOISE" << endl;
				exit(0);
			}

			if (i < size && input[i] == '1') {
				while (i < size && input[i] == '1') {
					if (i + 3 < size && ( input.substr(i + 1, 3) == "100" || input.substr(i + 1, 2) == "01")) {
						i++;
						break;
					}
					i++;
				}
			}
			else {
				cout << "NOISE" << endl;
				exit(0);
			}
		}

		if (input[i] == '0') {
			if (i + 1 < size && input.substr(i, 2) == "01") {
				i = i + 2;
			}
			else {
				cout << "NOISE" << endl;
				exit(0);
			}
		}
	}

	cout << "SUBMARINE" << endl;
	return 0;
}

풀이 2

오토마타 이용

유한 오토마타를 이용하는 방법이다. 오토마타에 대한 정리는 아래의 여기에 잘 되어있다.

우선 결론만 말하자면 오토마타는 상태 집함 Q, 상태 전이 함수 δ, 초기 상태를 나타내는 S0, 최종 상태 집합 F 등으로 구성된다.

위의 문제를 오토마타를 구성했을 때의 표는 다음과 같다.

	S0	"1"	"10"	"100~"	"100~1"	"100~1~"	"100~1~0"	"0"	"01"	F0
Q의 인덱스	0	1	2	3	4	5	6	7	8	9
'0'	7	2	3	3	7	6	3	9	7	9
'1'	1	9	9	4	5	5	8	8	1	9

해당 표는 이전 문자열(상태)에서 현재 어떤 문자에 나오냐에 따라 어떤 상태로 전이되느냐를 나타낸다. 초기 상태(S0)은 비교를 시작하지 않은 상태이고 첫 문자가 '0'인 경우 7번 인덱스를 타고 상태 "0"으로 전이되고, '1'인 경우 1번 인덱스를 타고 상태 "1"로 전이된다.

현재 표 내에서 상태집합을 보았을 때 SUBMARINE을 만족하는 문자열인 상태의 인덱스는 4, 5, 8이 있다. 이를 코드로 나타내면 다음과 같다.

using namespace std;

int p[11][2] = { {7,1},{2,9},{3,9},{3,4},{7,5},{6,5},{3,8},{9,8},{7,1},{9,9} };
int n;
string s;

int main() {
    cin >> s;
    for (int i = 0; i < s.length(); i++) {
        n = p[n][s[i] - '0'];
    }
    if (n == 4 || n == 5 || n == 8) { 
        cout << "SUBMARINE";
    }
    else { 
        cout << "NOISE";
    }

    return 0;
}

사전에 문제 내에서 규칙을 찾고 오토마타로 나타낸 표를 잘 구성하는 것이 중요한 것 같다.