[Algorithm] 백준 5052 전화번호 목록 - C++, 트라이

5052번: 전화번호 목록

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

struct Trie
{
    bool bIsTerminal;
    Trie* Children[10];

    Trie()
    : bIsTerminal(false), Children()
    {}

    ~Trie()
    {
        delete [] Children;
    }

    void Insert(const string& InputNumber)
    {
        Trie* CurTrie = this;

        for(int i = 0; i < InputNumber.size(); i++)
        {
            if(CurTrie->Children[InputNumber[i] - '0'] == nullptr)
            {
                CurTrie->Children[InputNumber[i] - '0'] = new Trie();        
            }
            CurTrie = CurTrie->Children[InputNumber[i] - '0'];

            if(i == InputNumber.size() - 1)
            {
                CurTrie->bIsTerminal = true;
            }
        }
    }

    bool IsTherePrefix(const string& InputNumber)
    {
        Trie* CurTrie = this;

        for(int i = 0; i < InputNumber.size(); i++)
        {
            if(CurTrie->Children[InputNumber[i] - '0'] != nullptr)
            {
                CurTrie = CurTrie->Children[InputNumber[i] - '0'];
                if(CurTrie->bIsTerminal)
                {
                    return true;
                }
            }
            else
            {
                return false;
            }
        }
        return false;
    }
};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    int TestCaseNum, PhoneNumberCount;

    cin >> TestCaseNum;

    while (TestCaseNum--)
    {
        cin >> PhoneNumberCount;
        vector<string> NumberList(PhoneNumberCount);
        for(int i = 0; i < PhoneNumberCount; i++)
        {
            cin >> NumberList[i];
        }

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

        Trie* NumberTrie = new Trie();
        bool bNotConsistency = true;
        
        for(auto PhoneNumber : NumberList)
        {
            if(NumberTrie->IsTherePrefix(PhoneNumber))
            {
                bNotConsistency = false;
                break;
            }
            NumberTrie->Insert(PhoneNumber);
        }

        if(bNotConsistency)
        {
            cout << "YES\n";
        }
        else
        {
            cout << "NO\n";
        }
        
        delete NumberTrie;
    }
}

 

---

 

시간적 여유가 생겨 새 알고리즘을 공부한 결과입니다. 트라이라는 자료구조를 처음 알게 되었기에 다른 자료들을 많이 참고하면서 풀이를 했습니다.