🔍 1013 Contact

최근 김동혁 박사는 아레시보 전파망원경에서 star Vega(직녀성) 으로부터 수신한 전파 기록의 일부를 조사하여 그 전파들의 패턴을 분석하여 아래와 같이 기록하였다.

(100+1+ | 01)+

김동혁 박사는 다양한 전파 기록 중에서 위의 패턴을 지니는 전파를 가려내는 프로그램을 필요로 한다. 이를 수행할 수 있는 프로그램을 작성하라.

---

🤔 풀이1 - 상태 기계 (state machine)

• finite state machine을 그려 문제를 해결할 수 있다.
  
• 하지만 100+1+이 나온 후, 마지막이 1이 해당 숫자의 끝인지 아니면 다른 100+1+의 시작인지 알 수 없다. 따라서 5, 6번 state를 추가해 처리해주어야 한다.
  eg) 10011001 → 10011 / 001 과 1001 / 1001 로 인식될 수 있다.
• 다음은 완성된 state machine(DFA) 이다. start state는 0. accepting state는 0, 4, 5, 8 이다. (순서대로 예시 100101, 1001, 10011, 01)
  
• 만약 state 1, 2, 7 과 같이 그림상에서 transition 이 하나밖에 나타나지 않을 때, 옳지않다는 뜻인 -1로 transition function 을 구성해주어야 한다. 해당 -1로 문자열이 옳은지, 다음 상태로 진행할 수 있는지 판단한다.
  eg) q({state1}, 0) → {state2}, q({state1}, 1) → {-1}
• (오토마타에서 배우고 후에 사용해본적이 손에 꼽는데 이렇게 사용하게 되어 신기했다. 대충 공부해서 가물가물한 상태라는게 아쉽다.)

---

📝 코드1

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

int T;
string s;
int state[9][2] = { {7, 1},
                    {2, -1},
                    {3, -1},
                    {3, 4},
                    {7, 5},
                    {6, 5},
                    {3, 0},
                    {-1, 8},
                    {7, 1} };

int main() {
    cin >> T;

    while (T--) {
        cin >> s;
        int states = 0;
        int isPattern = 1;
        for (int i = 0; i < s.length(); i++) {
            if ((states = state[states][s[i]-'0']) == -1) {
                isPattern = 0;
                break;
            } 
        }
        if (isPattern && (states == 0 || states == 4 || states == 5 || states == 8)) cout << "YES\n";
        else cout << "NO\n";
    }

    return 0;
}

---

🤔 풀이2 - regex(정규표현식 라이브러리)

• 정규표현식을 다루는 헤더 regex가 존재한다.

• regex_match(string, regex) 는 해당 string이 정규표현식 regex를 만족하는지 여부를 리턴한다.

---

📝 코드2

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

int T;
string s;

int main() {
    cin >> T;

    while (T--) {
        cin >> s;
        if (regex_match(s, regex("(100+1+|01)+"))) cout << "YES\n";
        else cout << "NO\n";
    }

    return 0;
}