728x90
728x90

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

 

2671번: 잠수함식별

입력에 들어있는 스트링을 읽고, 이것이 잠수함의 엔진소리를 나타내는 스트링인지 아니면 그냥 물속의 잡음인지를 판정한 후, 잠수함의 엔진 소리에 해당하는 스트링이면 "SUBMARINE"을 출력하고

www.acmicpc.net

 

 

문제

일반적으로 잠수함 엔진이 작동할 때에 나오는 소리는 잠수함의 종류에 따라서 다르다고 한다.

우리는 물속에서 들리는 소리의 패턴을 듣고서 그 소리가 특정한 잠수함에서 나오는 소리인지 아닌지를 알아내려고 한다. 이 문제에서는 잠수함의 소리가 두 종류의 단위 소리의 연속으로 이루어져 있고, 그 단위 소리를 각각 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' 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)

 

 

728x90

+ Recent posts