[λ°±μ€€] 1013 Contact

eunbiΒ·2022λ…„ 8μ›” 20일
0
post-thumbnail

πŸ” 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;
}

0개의 λŒ“κΈ€