BOJ 5052 : 전화번호 목록

• 문제 링크 : boj.kr/5052
• 난이도 : G4
• 태그 : 트라이

5052번: 전화번호 목록

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

class Trie {
    bool leaf;
    Trie* node[10];
public:
    Trie() {
        leaf = false;
        for(auto &u : node) {
            u = NULL;
        }
    }
    ~Trie() {
        for(auto u : node) {
            delete u;
        }
    }
    bool insert(string s) {
        if(s.length() == 0) {
            leaf = true;
            for(auto u : node) {
                if(u) return true;
            }
            return false;
        }
        int idx = s[0] - '0';
        if(node[idx] == NULL) {
            node[idx] = new Trie();
        }
        return leaf || node[idx]->insert(s.substr(1));
    }
};

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int T;
    cin >> T;
    while(T--) {
        int n;
        cin >> n;
        vector<string> arr(n);
        for(auto &u : arr) cin >> u;
        bool ans = false;
        Trie root;
        for(auto u : arr) {
            ans |= root.insert(u);
        }
        cout << (ans ? "NO" : "YES") << "\n";
    }

    return 0;
}

---

풀이

트라이 기본문제이다.

정렬해서 푸는 방법도 있다.