[C++] 백준 2671번 - 잠수함 식별 (정규 표현식, 완전 탐색)

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

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

 

 

---

 

접근 방법

주어진 식은 (100~1~|01)~ 이다.

 

- part A : 100~

- part B : 1~

 - part C = 01

이라고 하자. 

그 후, next State = cur State + next Char 형식에 맞춰서 나올 수 있는 모든 경우를 계산해보면 다음과 같다.

cur State	next Char	next State = cur State + next Char	next State가 현재 뜻하는 부분
Init	'0'	"0"	part C
Init	'1'	"1"	part A
"0"	'0'	X	part C 의 0 다음에는 바로 1이 나와야 함->바로 아래 행만 해당됨
"0"	'1'	"01"	part C
"1"	'0'	"10"	part A
"1"	'1'	X	part A의 1 다음에는 바로 0이 나와서 100~ 의 형식이 되어야 함
"01"	'0'	"0"	part C 끝나고 다시 part C 가 된 것이므로 초기화
"01"	'1'	"1"	part C 끝나고 다시 part A 가 된 것이므로 초기화
"10"	'0'	"100"	part A
"10"	'1'	X	part A는 100~ 형식이므로, 101은 형식에 어긋남.
"100"	'0'	"100~"	part A
"100"	'1'	"100~1"	part A -> part B로 넘어가는 부분. 원래 "1001"이지만 "100~1"에 포함되므로 "100~1"로 표기.
"100~"	'0'	"100~"	part A 원래 "100~0"이지만 "100~"에 포함되므로 "100~"로 표기.
"100~"	'1'	"100~1"	part A -> part B로 넘어가는 부분
"100~1"	'0'	"0"	part C part A -> part B까지 끝나고 part C가 시작된 것이므로 초기화.
"100~1"	'1'	"100~1~"	part A -> part B가 된 상태.
"100~1~"	'0'	"10 or 0"	part A -> part B가 된 상태에서 두가지 상태로 나뉨. case 1) part A -> part B -> part A  : "10" case 2) part A -> part B -> part C : "0"
"100~1~"	'1'	"100~1~"	원래 "100~11"이지만 "100~1~"에 포함되므로 "100~1~"로 표기.
"10 or 0"	'0'	"100"	partA case 1)의 part A 를 뜻하는 "10" 다음에 '0'이 온 것은 "100"임. case 2)의 part C를 뜻하는 "0"다음에 '0'이 온 것은 형식에 어긋나므로 배제.
"10 or 0"	'1'	"01"	part C case 1)의 part A 를 뜻하는 "10" 다음에 '1'이 온 것은 형식에 어긋나므로 배제. case 2)의 part C를 뜻하는 "0"다음에 '1'이 온 것은 part C의 "01" 형식에 적합.

이렇게 구한 값은 unordered_map<string, vector<string>> umap에 넣어주면 된다.

이때 주의할 점은 value에 해당하는 vector에 nextState값을 넣을 때 인덱스를 고려해서 넣어야한다. 즉, next Char 이 0이면 vector의 0번째 인덱스 [0]에 넣어주고, 1이면 1번째 인덱스[1]에 넣어준다. 그래야 입력된 문자열을 한 글자씩 따라가면서 주어진 형식을 어긋나지 않는지 검사할 수 있다.

 

그렇게 입력된 문자열을 다 검사한 뒤에, state의 값을 검사한다. 이때 잠수함 엔진소리라면 

case 1) part A -> part B에서 끝나거나

case 2) part C 에서 끝나야 한다. 

 

case 1)은 "100~1" 와 "100~1~"이 해당되고, case 2)는 "01"이 해당된다.

 

마지막 state 값이 이 세가지 중 하나라면 잠수함 엔진소리가 맞고, 그 외는 엔진소리가 아니다.

 

//
//  BF_BOJ2671_잠수함식별.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/07/06.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//


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

int main(){
    
    string str;
    cin >> str;
    
    unordered_map<string, vector<string>> umap;
    
    umap["init"] = {"0","1"};
    umap["0"] = {"X", "01"};
    umap["1"] = {"10", "X"};
    umap["01"] = {"0", "1"};
    umap["10"] = {"100", "X"};
    umap["100"] = {"100~", "100~1"};
    umap["100~"] = {"100~", "100~1"};
    umap["100~1"] = {"0", "100~1~"};
    umap["100~1~"] = {"10 or 0", "100~1~"};
    umap["10 or 0"] = {"100", "01"};
    
    string state = "init";
    for(int i = 0; i<str.length(); i++){
        int nextChar = str[i] - '0';
        state = umap[state][nextChar];
        if(state == "X") break;
    }
    
    if(state == "100~1" || state == "100~1~" || state =="01") cout << "SUBMARINE";
    else cout << "NOISE";
    
    
    
    return 0;
}

 

(사실 <regex> 라이브러리를 활용하면 한 줄로 끝난다.)

 

참고  : (https://gglifer-cs.tistory.com/74)