[BOJ] 2671 : 잠수함 식별

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

---

문자열 문자열처리

(100~1~|01)~ 를 만족하는지 아닌지 판단하면 된다.

● (100~1~|01)~ 는 100~1~ 과 01의 조합으로 이루어져있다. 따라서, 0으로 시작하면 "01" 이고, 1로 시작하면 "100~1~" 임을 알 수 있다.

● 0으로 시작하면 "01" 을 제외하고 다 NOISE인 경우이다.  따라서, 0을 만나면 다음 칸이 1인지 체크하고 맞다면 2칸 앞으로 건너뛰면 된다.

● 1로 시작하면 100~1~ 이다. 이때, 100 / 1 은 무조건 존재해야한다. 먼저, 1을 만나면 뒤에 0이 2개 있는지 체크하고, 1000000 과 같지 100~ 에 해당되는 0들을 다 건너뛴다. 그 후, 111111과 같이 1~에 해당되는 부분들을 다 건너 뛴다. 이때, 체크해줘야하는 부분이 있다. 100~ 에 해당되는 부분이 다 끝나고, 1~ 로 해당되는 부분은 11111111과 같이 1이 여러 번 반복되도 된다. 하지만, 10011001 과 같이 1001 / 1001 로 나눠지는 경우에는 10011 까지 1을 반복해서 앞에 부분으로 종속시키면 안되므로, 현재 '1' 인데 뒤에 "00" 이 붙은 경우는 다시 위에부터 순회를 진행해주면 된다.

반례

1001001 : NOISE

1000001110000001 : SUBMARINE

#include<iostream>
#include<string>

using namespace std;

bool checkAns(string N) {
	int i = 0, s = N.length();
	while (i < s) {
		if (N[i] == '0') {
			if (i + 1 >= s) return false;
			if (N[i + 1] != '1') return false;
			i += 2;
		}
		else { // 시작이 1이면 최소 1 00 1
			if (i + 3 >= s) return false;
			if (!(N[i + 1] == '0' && N[i + 2] == '0')) return false; // 일단 무조건 뒤에 0이 2개 나와야됨.
			i++;
			while (i < s && N[i] == '0')
				i++;
			if (i >= s) return false; // 1 뒤에붙은 0들을 다 추적했더니 끝나버린 경우.
			i++;
			while (i < s && N[i] == '1') {
				if (i + 2 < s && N[i + 1] == '0' && N[i + 2] == '0') break;
				i++;
			}
		}
	}
	return true;
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	string s;
	cin >> s;
	if (checkAns(s)) cout << "SUBMARINE";
	else cout << "NOISE";
	return 0;
}

---