문제 푼 날짜 : 2021-09-22

문제

문제 링크 : https://www.acmicpc.net/problem/5052

접근 및 풀이

이 문제를 어떻게 풀어야할지 고민하다가, 알고리즘 분류에 '트라이'라고 적혀있는 것을 보았다.
문제를 보고 스스로 떠올렸어야 했는데,,, 트라이를 보자마자 문제가 너무 쉽게 느껴졌다.
트라이에 관한 설명은 이 곳에 아주 잘되어있으니 참고하면 될 것 같다.

1. 트라이를 구현해준다.(입력, 탐색까지)
2. 모든 문자열(전화번호)을 삽입해주고, 그 전화번호들을 각각 탐색해준다.
3. 각 전화번호의 탐색이 끝났을 때, 마지막 번호에 해당하는 노드의 count 값이 1이 아니라면, 그 전화번호를 접두어로 한 또다른 전화번호가 존재한다는 뜻이므로 false를 반환해주었다.

ex) 아래는 911, 91125라는 전화번호가 있을 때의 트라이 예시이다.
노드는 해당 위치에서 몇 개의 전화번호가 존재하는지를 나타내주고 간선들은 전화번호의 각 번호를 나타내어준다.
911을 탐색했을 때 마지막 노드의 값이 2 이므로 이를 통해 911을 접미사로 하는 다른 전화번호가 존재함을 알 수 있다.

코드

// 백준 5052번 : 전화번호 목록
#include <iostream>
#include <vector>

using namespace std;

class Trie {
    private :
        int count;
        Trie *number[10];

    public :
        Trie() : count(0), number() {}

        void Insert(string str) {
            Trie *curr = this;
            curr->count++;

            for (char ch : str) {
                if (curr->number[ch - '0'] == nullptr) {
                    curr->number[ch - '0'] = new Trie();
                }
                curr = curr->number[ch - '0'];
                curr->count++;
            }
        }
        bool Search(string str) {
            Trie *curr = this;

            int ret = curr->count;
            for (char ch : str) {
                curr = curr->number[ch - '0'];
                ret = curr->count;
            }
            if (ret == 1) {
                return true;
            } else {
                return false;
            }
        }
};


int main() {
    int t, n;

    cin >> t;

    while (t--) {
        cin >> n;
        string number = "";
        vector<string> v;
        Trie *tri = new Trie();
        
        while (n--) {
            cin >> number;
            v.push_back(number);
            tri->Insert(number);
        }
        bool flag = true;
        for (string str : v) {
            if (!tri->Search(str)) {
                flag = false;
                break;
            }
        }
        if (flag) {
            cout << "YES" << '\n';
        } else {
            cout << "NO" << '\n';
        }
    }
    return 0;
}

결과

피드백

유사한 문제로 카카오 코딩테스트 문제인 자동완성 과 가사 검색이 있다.