BOJ 5052 전화번호 목록

www.acmicpc.net/problem/5052

5052번: 전화번호 목록

 

트라이를 사용하는 문제지만 map을 활용해서 접두사 트리를 만들고 전화번호를 만드는 중에 이미 존재하는 전화번호가 있다면 YES 아니면 NO를 출력해주면 된다.

map을 <string, bool> 로 선언하고 string 부분은 전화번호, bool 부분은 완성된 전화번호인지? 를 판단하는 변수다

 

<9,1>

<91,1>

<911,2>

 

이런 식으로 처리해줘서 중간에 2가 나온다면 접두사에 완전한 전화번호가 존재한다는 뜻이니 NO를 출력해주면 된다.

 

 

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
 
unordered_map<string, int> m;
string s[10001];
int tc, n;
 
inline bool go() {
    for (int i = 0; i < n; ++i) {
        string tmp;
        for (int c = 0; c < int(s[i].size()) - 1; ++c) {
            tmp += s[i][c];
            if (m[tmp] == 2) return false;
        }
    }
    return true;
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    cin >> tc;
    while (tc--) {
        cin >> n;
        m.clear();
        for (int i = 0; i < n; ++i) {
            cin >> s[i];
            string tmp;
            for (int c = 0; c < s[i].size(); ++c) {
                tmp += s[i][c];
                if (m[tmp] == 0) m[tmp] = 1;
            }
            m[tmp] = 2;
        }
 
        if (go()) cout << "YES" << '\n';
        else cout << "NO" << '\n';
    }
 
    return 0;
}