5052 전화번호 목록

5052. 전화번호 목록 / c++ / Gold4 / 45분

문제

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

1. 테스트 케이스 t (1 <= t <= 50)
2. 각 테스트 케이스마다 전화번호의 수 n (1 <= n <= 10’000)
3. 한 전화번호가 다른 전화번호를 포함하고 있으면 일관성이 없는 목록
4. 같은 전화번호는 주어지지 않을 때, 일관성이 있다면 “YES” 없다면 “NO”를 출력

접근 방식

자료구조, 트라이

1. string A와 B가 있을 때 (B의 길이가 A와 같거나 큼) B.substr(0, A.length()) == A 이면 NO를 출력하려고 했다. (시간초과)
2. set에 넣어서 판별해봤다 (시간초과)
3. 문득 어디선가 봤던 알고리즘이 생각났다. 만약 번호가 91125426 이라고 한다면
   9 -> 1 -> 1 -> 2 -> 5 -> 4 -> 2 -> 6 이런 순으로 트리를 타고 들어가는 것이다.
4. 이 때, 번호 911은 9 -> 1 -> 1 로 들어가게 되는데, 만약 이미 9 -> 1 -> 1 로 들어온 번호가 있다면 NO를 출력하면 된다.
5. 우선 노드를 만들고 이 노드를 몇번이나 지나쳤는지를 나타내는 ‘data’와, 이 노드에서 다시 0~9로 뻗어나가는 ‘nextNumber’ 를 만들고,
6. 전역변수로 Node* head를 선언한 다음, 번호마다 head부터 파고들어가는 식으로 체크했다.
7. 그리고 번호가 끝나는 순간 이 노드를 지나간 다른 번호가 있는지를 체크해야 했으므로, 긴 번호부터 짧은 번호 순으로 진행했다. (짧은 번호가 긴 번호에 포함되므로)

문제 풀이

#pragma GCC optimize("Ofast")
#include <iostream>
#include <queue>
#include <string>
using namespace std;

struct Node
{
    int data = 0;
    Node* nextNumber[10] = { nullptr, nullptr, nullptr, nullptr, nullptr, nullptr, nullptr, nullptr, nullptr, nullptr };

    ~Node()
    {
        for (int i = 0; i < 10; ++i)
        {
            if (nextNumber[i] != nullptr) delete nextNumber[i];
        }
    }
};

int T, N;
string number;

struct COMP
{
    bool operator()(string a, string b)
    {
        if (a.length() == b.length()) return a < b;

        return a.length() < b.length();
    }
};

priority_queue<string, vector<string>, COMP> pq;

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

    cin >> T;

    while (T-- > 0)
    {
        cin >> N;

        while (N-- > 0)
        {
            cin >> number;
            pq.push(number);
        }

        Node* head = new Node();
        bool isCorrect = true;

        while (!pq.empty())
        {
            Node* nowNode = head;
            for (int i = 0; i < pq.top().length(); ++i)
            {
                int pos = pq.top()[i] - '0';
                if (nowNode->nextNumber[pos] == nullptr)
                {
                    nowNode->nextNumber[pos] = new Node();
                }

                nowNode = nowNode->nextNumber[pos];
                if (i == pq.top().length() - 1 && nowNode->data > 0)
                {
                    isCorrect = false;
                    break;
                }
                nowNode->data++;
            }

            pq.pop();
        }

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

        delete head;
    }

    return 0;
}

다시 생각해 볼 점

1. 나중에 알고 보니 이게 트라이 (Trie)라는 자료구조 였다. (트리로 문자열을 저장하는 방식)