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
를 비교한다
엔진 소리 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; }