[백준/BOJ] 5052번 : 전화번호 목록 (트라이, Trie)

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge의 5052번 : '전화번호 목록' 문제의 풀이 코드와 해설을 다루고 있습니다.

 

문제 난이도는 Solved.ac 기준 Gold IV에 해당하며, 문제를 풀이하기 위해 자료구조의 일종인 '트라이'에 대한 이해가 필요합니다.

 

 

5052번 : 전화번호 목록

 

주어진 전화번호 목록 중에서, 어떤 하나의 번호가 다른 번호의 접두사에 해당할 때 NO를 출력하고 그 외에는 YES를 출력해주면 되는 문제입니다.

이를 주어진 제한 시간 안에 빠르게 검색할 수 있도록 구현하기 위해 자료구조 '트라이'를 구현해볼 것입니다.

 

트라이는 문자열 길이 m에 대해 O(m) 시간에 문자열을 검색할 수 있는 효율적인 문자열 탐색용 자료구조입니다.

문자의 종류가 K개라고 할 때, K진 트리의 구조 즉, 특정 문자 다음에 올 수 있는 문자들을 모두 자식 노드로 가지고 있습니다.

 

 

 

예를 들어보겠습니다.

위와 같이 abc, abd, aca, bac, bad라는 단어를 트라이에 저장한다고 하면 트라이는 위와 같은 구조를 가지게 됩니다.

이제 위와 같은 트라이를 0~9의 문자로 이루어진 형태로 구현하여 문제를 풀이해보겠습니다.

 

 

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

struct Trie {
    Trie *next[10];
    bool isEnd, isChild;

    Trie() {
        fill(next, next+10, nullptr);
        isEnd = isChild = false;
    }

    ~Trie() {
        for(int i=0; i<10; i++)
            if(next[i]) delete next[i];
    }

    bool insert_(char *key) {
        if(*key == '\0') {
            isEnd = true;
            if(isChild) return false;
            else return true;
        }

        int nextKey = *key - '0';
        if(!next[nextKey]) next[nextKey] = new Trie;
        isChild = true;

        if(!isEnd && next[nextKey]->insert_(key + 1)) return true;
        else return false;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int T; cin >> T;
    while(T--) {
        Trie *root = new Trie;
        bool check = true;

        int N; cin >> N;
        for(int i=0; i<N; i++) {
            char num[11]; cin >> num;
            if(check && !root->insert_(num)) check = false;
        }

        if(check) cout << "YES\n";
        else cout << "NO\n";

        delete root;
    }
}

 

우선 Trie라는 struct를 만들어주고, 각 테스트케이스에 대해 Trie를 새로 생성해야 하고 메모리 낭비를 줄여야하므로 생성자와 소멸자를 모두 구현해줍니다.

insert_ 함수는 새로운 keyword를 트라이에 insert 해주는 함수입니다.

노드들을 따라 내려가며 이미 존재하는 접두사까지는 내려가고 그 뒤부터 key 값들을 각각의 노드들을 생성하여 저장해줍니다.

또한 insert_ 함수는 void 형이 아닌 bool 형으로 구현하여 어떤 단어를 이미 포함하고 있다면 true를 반환하도록 합니다.

 

 

 

풀이를 제출하면 위와 같은 기록으로 모든 테스트케이스를 통과할 수 있습니다.