[백준] 2671번 : 잠수함식별 (C++)

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

2671번: 잠수함식별

2가지 방법을 이용하여 풀었다.

1. 문자열 처리 (이런 패턴을 찾아서 푸는걸 Finite Automata라고 부르는것 같다)

2. 정규표현식 Regex을 이용

 

이 문제에서는 (100~1~|01)~ 에 해당하는 패턴을 찾는 것이었다.

따라서, 모든 문자열은 100~1~ 와 01의 조합으로만 구성되어야 한다! 각각의 조합을 1번과 2번이라고 해보자.

1번 : 100~1~

2번 : 01

 

맨 앞문자가 0으로 시작하는 문자는 2번 조합만 가능하므로 0뒤에 1이오면 01이라고 간주하고 인덱스를 +2하고 넘어갔다.

맨 앞문자가 1로 시작하는 경우는 1번 조합만 가능하다. 1 바로 뒤부터 연속된 0이 최소 2번이 나와야하기 때문에, while()문을 통해 1 뒤에 연속된 0의 개수를 zerocnt변수를 통해 카운팅해주었다.

zerocnt가 2미만이면 즉시 종료하였고, 그게 아니라면 연속된 0뒤에는 반드시 1이 있어야 되기 때문에 이를 체크해주었다. 여기까지하면 100~1~를 만족하게 된다. 

 

핵심은 지금부터이다

100~1~의 최소조건은 만족하였지만 1뒤에 1이 또 연달아 나오는 경우를 주의해야한다.

11111 → 쭉 1이 나오면 1번 조합의 형태를 유지하는 것이므로 계속 진행하면 된다.

11101 → 쭉 1이 나오다가 "0"이 나오면 2번 조합의 시작을 의미한다. 2번조합이 맞는지는 위에서 다시 체크해준다.

11100 → 쭉 1이 나오다가 "00"이 나오면 1번 조합의 재시작을 의미한다. 즉, 11/100로 구분해야한다. (제일중요)

 

따라서, 100~1~의 최소조건인 100...00001까지 만족했다면 그다음부턴 "100" 형태를 찾으면 해당 1번 인덱스부터 1번의 조합을 재시작하고, "0"을 찾으면 2번 조합을 재시작하면 되는 것이다.

전체 코드는 아래와같다.

 

문자열 처리를 통한 풀이

#include <iostream>
using namespace std;

string s;

int main() {
	cin >> s;
	bool flag = true;

	int cur = 0;
	while (flag && cur<s.size()) {
		if (s[cur] == '0') {
			if (cur + 1 < s.size() && s[cur + 1] == '1') {
				cur += 2;
			}
			else flag = false;
		}
		else {//1로시작
			int zerocnt = 0;
			while (cur< s.size() && s[++cur] == '0') zerocnt++; //100~1 부분검사
			if (zerocnt < 2 || cur==s.size()) flag = false; //0이 2개 미만이거나 1이 모자라는 경우
			else {//100~1까지 통과. 100~1~확인
				cur++; //100~1 다음인덱스 
				while (true) {
					if (cur >= s.size() || s[cur] == '0') break; //범위 벗어나거나 2번쨰 패턴 시작
					if (cur + 2 < s.size() && s.substr(cur, 3) == "100") break; //100이면 1번째 패턴 시작
					cur++; //1로시작하지만 101,100패턴이 아닌경우
				}
			}

		}
	}
	cout << (flag ? "SUBMARINE" : "NOISE") << endl;
}

 

정규표현식을 이용한 풀이

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

int main() {
	string s;
	cin >> s;
	cout << (regex_match(s, regex("(100+1+|01)+")) ? "SUBMARINE": "NOISE") << endl;
}