[BOJ] 5052 - Phone List

https://www.acmicpc.net/problem/5052

BOJ - Phone List

문제 유형: 문자열 처리, 트라이, 정렬

문제 난이도: Gold IV

 

문제

전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오.

전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다.

예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자

• 긴급전화: 911
• 상근: 97 625 999
• 선영: 91 12 54 26

이 경우에 선영이에게 전화를 걸 수 있는 방법이 없다. 전화기를 들고 선영이 번호의 처음 세 자리를 누르는 순간 바로 긴급전화가 걸리기 때문이다. 따라서, 이 목록은 일관성이 없는 목록이다.

 

입력

첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 하나씩 주어진다. 전화번호의 길이는 길어야 10자리이며, 목록에 있는 두 전화번호가 같은 경우는 없다.

 

출력

각 테스트 케이스에 대해서, 일관성 있는 목록인 경우에는 YES, 아닌 경우에는 NO를 출력한다.

 

풀이

Trie의 노드에 문자열의 종료여부와 자식가능성이 있는 10개의 배열 슬롯을 만든다. 만약 다음글자가 '1'이면 인덱스 1에 다음 Trie노드에 대한 주소값이 있는 것이다.

트라이를 선언하며 루트 노드를 하나 만들어둔다.

전화번호 문자열 목록을 받아서(문자열로 받아야 한다. prefix 0이 trim될수 있기 때문이다.) 정렬한다. 

사전순 정렬을 하면, prefix의 가능성이 있는 문자열이 더 앞에 오게 된다.

 

순서대로 트라이에 넣는 것을 시도한다. 만약 prefix 발견 시, 즉시 탈출해서 "NO"를 출력해도 된다.

모든 입력이 정상적으로 삽입에 성공했다면, "YES"를 출력한다.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

struct TrieNode {
    bool isEnd;
    vector<TrieNode*> children;
    TrieNode() {
        isEnd = false;
        children.resize(10, nullptr);
    }
};

struct Trie {
    TrieNode* root;
    Trie() { root = new TrieNode(); }

    bool insert(string str) {
        bool flag = false;
        TrieNode* p = root;
        for (int i = 0; i < str.size(); i++) {
            int next = str[i] - '0';
            if (p->children[next] == nullptr)
                p->children[next] = new TrieNode();
            p = p->children[next];
            flag |= p->isEnd;
        }
        p->isEnd = true;
        return flag;
    }
};

void solve() {
    int n;
    cin >> n;
    Trie* t = new Trie();
    vector<string> contracts(n);

    for (int i = 0; i < n; i++) {
        cin >> contracts[i];
    }

    sort(contracts.begin(), contracts.end());

    for (const auto& str : contracts) {
        if (t->insert(str)) {
            cout << "NO\n";
            return;
        }
    }

    cout << "YES\n";
}

int main(int argc, char* argv[]) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}