[ 백준 ] 2671 / 잠수함식별

金弘均·2021년 9월 16일
0

Baekjoon Online Judge

목록 보기
157/228
post-thumbnail

# Appreciation

/*
 * Problem :: 2671 / 잠수함식별
 *
 * Kind :: Automata
 *
 * Insight
 * - 간단한 정규표현식 문제는 오토마타로 풀자~
 *   + (100~1~|01)~
 *     "100~1~" 과 "01" 로 이루어진 스트링인지 판별해야한다
 *     # State + Next Char = Next State
 *
 *       "INIT" + '0' = "0"
 *       "INIT" + '1' = "1"
 *
 *       "1" + '0' = "10"
 *       "1" + '1' = "11" / No Submarine <= "100~1~" 또는 "01" 이 될 수 없음
 *
 *       "10" + '0' = "100"
 *       "10" + '1' = "101" / No Submarine <= "100~1~" 또는 "01" 이 될 수 없음
 *
 *       "100" + '0' = "100~"
 *       "100" + '1' = "100~1"
 *
 *       "100~" + '0' = "100~"
 *       "100~" + '1' = "100~1" / Submarine
 *
 *       "100~1" + '0' = "0" / "100~10" => "0"
 *       "100~1" + '1' = "100~1~" / Submarine
 *
 *       "100~1~" + '0' = "10 or 0"
 *       "100~1~" + '1' = "100~1~"
 *
 *       "10 or 0" + '0' = "100"
 *       "10 or 0" + '1' = "01" / Submarine
 *
 *       "0" + '0' = "00" / No Submarine <= 100~1~" 또는 "01" 이 될 수 없음
 *       "0" + '1' = "01" / Submarine
 *
 *       "01" + '0' = "0"
 *       "01" + '1' = "1"
 *
 * Point
 * - "100~1~" 에서 '0' 이 추가될때
 *   이는 "10" 의 상태를 뜻할수도 있고 "0" 의 상태를 뜻할 수도 있다
 *   + 이 상태에서 '1' 이 추가된다면 현재 상태를 "0" 으로 보아 "01" 상태로 넘어가야 하고
 *     '0' 이 추가된다면 현재 상태를 "10" 으로 보아 "100" 상태로 넘어가야 한다
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <vector>
#include <map>

using namespace std;

#define endl '\n'

// Set up : Global Variables
/* None */

// Set up : Functions Declaration
/* None */


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    string sound; cin >> sound;

    // Process
    string NO = "NO";
    string INIT = "INIT";
    map<string,vector<string>> next; /* 다음상태 = next[현재상태][다음글자] */
    next["INIT"] = {"0", "1"};
    next["1"] = {"10", NO};
    next["10"] = {"100", NO};
    next["100"] = {"100~", "100~1"};
    next["100~"] = {"100~", "100~1"};
    next["100~1"] = {"0", "100~1~"};
    next["100~1~"] = {"10 or 0", "100~1~"};
    next["0"] = {NO, "01"};
    next["01"] = {"0", "1"};
    next["10 or 0"] = {"100", "01"};

    string state = INIT;
    for (char c : sound) {
        int v = c - '0';
        state = next[state][v];
        if (state == NO) break; /* 이 소리는 잠수함 엔진소리일 수 없음 */
    }

    // Control : Output
    /* "100~1", "100~1~", "01" 상태인 경우에 잠수함 엔진소리임 */
    if (state == "100~1" || state == "100~1~" || state == "01")
        cout << "SUBMARINE" << endl;
    else
        cout << "NOISE" << endl;
}

// Helper Functions
/* None */
profile
이런 미친 게임을 봤나! - 옥냥이

0개의 댓글