<Baekjoon> #2671 Brute Force/regex_잠수함 식별 c++

2671 잠수함
참고1 참고2 참고3

1. std::regex 활용 (정규식)

정규 표현식은 문자열에서 패턴을 찾는데 사용

• 주어진 문자열이 주어진 규칙에 맞는지 확인할 때
• 주어진 문자열에서 원하는 패턴의 문자열을 검색할 때
• 주어진 문자열에서 원하는 패턴의 문자열로 치환할 때

주어진 엔진 소리 (100~1~|01)~은 정규식 (100+1+|01)+로 나타낼 수 있다.

#include <regex>
regex re("(100+1+|01)+");
if (regex_match(s, re)) cout << "SUBMARINE";
else cout << "NOISE";

여기서 regex_match를 통해 정규식 re와 엔진 소리s를 비교한다

2. brute force

엔진 소리 string s에서 s[0]~s[s.length()-1] 부터 차례대로 검사한다
엔진 소리가 0으로 시작되는 경우와 1로 시작되는 경우로 나누어 생각한다

• 0으로 시작되는 경우: '01' 로 시작하는 경우밖에 없다
  만약 s[i]=='0' 일 때, s[i+1]='1' 이어야 하므로 i+1은 s의 총 길이를 넘지 않아야 한다.

  		if (s[i] == '0') {
  			if (i + 1 >= n) return false;
  			if (s[i + 1] != '1') return false;
  			i += 2;
  		}

• 1로 시작하는 경우 : 최소 '1001'을 만족해야 한다
  s[i]=='1'인 경우 s[i+1]='0', s[i+2]='0'는 무조건 만족하고 뒤에 0 또는 1이 와야한다
  따라서 i+3이 s의 길이를 넘지 않아야 한다

  			if (i + 3 >= n) return false;
  			if (!(s[i + 1] == '0' && s[i + 2] == '0')) return false;
  			i++;

• 그 후 0이 반복해서 나오는 만큼 뛰어 넘고 마지막으로 뛰어 넘었을 때 이대로 끝나면 엔진 소리가 아니다 (뒤에 최소 1이 하나는 나와야 하기 때문에)

  			while (i < n && s[i] == '0') i++;
  			if (i == n) return false;
  			i++;

• 1이 나오는 만큼 뛰어 넘는다

  			while (i < n && s[i] == '1') 
  				i++;			

• 여기서 만약 10011001 과 같은 예시가 있다면 1001, 1001 과 같이 잘라서 읽어야 하는데 위에서 짠 코드대로 한다면 100 11 001 로 잘리기 때문에 false를 return 하게 된다. 그래서 만약 1뒤에 00이 연달아 온다면 이 과정을 무시하게 수정한다

  		while (i < n && s[i] == '1') {
  			if (i + 2 < n && s[i + 1] == '0' && s[i + 2] == '0') break;
  			i++;
  		}

전체 코드

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

bool isSubmarine(string s) {
	int i = 0, n = s.length();
	while (i < n) {
		if (s[i] == '0') {
			if (i + 1 >= n) return false;
			if (s[i + 1] != '1') return false;
			i += 2;
		}
		else {
			if (i + 3 >= n) return false;
			if (!(s[i + 1] == '0' && s[i + 2] == '0')) return false;
			i++;
			while (i < n && s[i] == '0') i++;
			if (i == n) return false;
			i++;
			while (i < n && s[i] == '1') {
				if (i + 2 < n && s[i + 1] == '0' && s[i + 2] == '0') break;
				i++;
			}
		}
	}
	return true;
}

int main() {
	string s;
	cin >> s;
	if (isSubmarine(s)) cout << "SUBMARINE";
	else cout << "NOISE";
	return 0;
}