BOJ 5052 - 전화번호 목록 링크
(2023.07.10 기준 G4)

문제

전화번호 목록이 주어지고, 이 목록이 일관성이 있기 위해선 한 번호가 다른 번호의 접두어인 경우가 없어야 한다. 이 때, 주어지는 목록이 일관성 유무 출력

알고리즘

간단한 정렬 후, 트라이로 문자열 비교

풀이

트라이는 문자열 여러 개를 빠르게 비교하기 위해 문자 하나하나를 문자열의 이어진 상태를 트리로 나타낸 것이다.

번호 A가 번호 B의 접두어라면, 번호 A의 길이는 번호 B의 길이보다 짧거나 같다. 절대 길 수 없다.
그러므로 주어지는 번호 목록을 번호의 길이가 내림차순이 되게끔 정렬하자.

그 후 번호 차례대로 트라이 객체에서 검색해보자. 만약, 검색한 문자열이 트라이 객체의 트리가 이어지게끔 탐색이 가능하다면 이미 검색한 문자열이 접두어인 번호가 있다는 것이다.예제 1번을 예시로 들면 이렇다.

검색을 실패하면 트라이 객체에 문자열을 삽입하자. 이어지는 문자 노드가 있다면 거기로, 없다면 새 노드를 만들어 이어주면 된다.

코드

• C++

#include <bits/stdc++.h>
using namespace std;

struct Node{
    map<char, Node> p; // 자식 노드
};

struct Trie{
    Node root;

    void init();

    void insert(string s){
        Node *here = &root; // 루트부터 시작

        for (char c: s){
            if (here->p.find(c) == here->p.end()) // 문자가 없다면 새 노드를 만들어 이어준다.
                here->p[c] = Node();
            here = &here->p[c]; // 다음 노드로
        }
    }

    bool search(string s){
        Node *here = &root; // 루트부터 시작

        for (char c: s){
            if (here->p.find(c) == here->p.end()) // 문자가 없다면 찾고자 하는 문자열이 없다는 것이다.
                return false;
            here = &here->p[c]; // 다음 노드로
        }

        // 문자열의 모든 문자를 찾아 왔다면 검색을 성공한 것이다.
        return true;
    }
}trie;

void Trie::init(){
    root.p.clear();
}

bool comp(string a, string b){
    return a.size() > b.size();
}

void solve(){
    int n; cin >> n;
    vector<string> lst(n);
    for (int i = 0; i < n; i++) cin >> lst[i];
    sort(lst.begin(), lst.end(), comp); // 길이가 내림차순이 되게

    trie.init();
    for (string number: lst){
        if (trie.search(number)){ // 번호를 찾았다면 일관성이 없다.
            cout << "NO" << '\n';
            return;
        }
        trie.insert(number);
    }

    cout << "YES" << '\n';
}

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

    int t; cin >> t;
    while (t--) solve();
}

• Python

import sys; input = sys.stdin.readline

class Node:
    def __init__(self):
        self.p = dict() # 자식 노드

class Trie:
    def __init__(self):
        self.root = Node()

    def insert(self, s):
        here = self.root # 루트부터 시작

        for c in s:
            if c not in here.p: # 문자가 없다면 새 노드를 만들어 이어준다.
                here.p[c] = Node()
            here = here.p[c] # 다음 노드로

    def search(self, s):
        here = self.root # 루트부터 시작

        for c in s:
            if c not in here.p: # 문자가 없다면 찾고자 하는 문자열이 없다는 것이다.
                return False
            here = here.p[c] # 다음 노드로

        # 문자열의 모든 문자를 찾아 왔다면 검색을 성공한 것이다.
        return True

for _ in range(int(input())):
    n = int(input())
    lst = sorted([input().strip() for _ in range(n)], key = lambda x: -len(x)) # 길이가 내림차순이 되게

    trie = Trie()
    for number in lst:
        if trie.search(number): # 번호를 찾았다면 일관성이 없다.
            print('NO')
            break
        trie.insert(number)
    else:
        print('YES')