백준 5052번 전화번호 목록

 

접두사를 찾는 문제로

 

트라이를 이용하여 간단하게 풀 수 있는 문제입니다.

 

트라이란? https://suhwanc.tistory.com/98

 

주어진 문자열들을 (0 ~ 9) 정렬한 후, 뒤에서 부터 트라이에 이 문자열이 있는지 find 하고

 

없으면 insert를 반복해 전화번호 목록의 일관성을 찾아내면 됩니다.

 

소스 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
 
int t; //test case
int n; //call number
const int NUMBER = 10; // '0' ~ '9'
 
int toNumber(char ch) { return ch - '0'; }
 
struct TrieNode {
    TrieNode* children[NUMBER];
    bool terminal;
    //생성, 소멸자
    TrieNode() : terminal(false) {
        memset(children, 0, sizeof(children));
    }
    ~TrieNode() {
        for (int i = 0; i < NUMBER; i++)
            if (children[i]) delete children[i];
    }
    //트라이에 번호 추가
    void insert(const char* key) {
        if (*key == 0) terminal = true;
        else {
            int next = toNumber(*key);
            if (children[next] == NULL)
                children[next] = new TrieNode();
            children[next]->insert(key + 1);
        }
    }
    //트라이에 번호 일치 확인
    TrieNode* find(const char* key) {
        if (*key == 0) return this;
        int next = toNumber(*key);
        if (children[next] == NULL) return NULL;
        return children[next]->find(key + 1);
    }
};
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> t;
    while (t--) {
        cin >> n;
        vector<string>input; //전화번호 길이 순 정렬
        for (int i = 0; i < n; i++) {
            char buf[11];
            cin >> buf;
            input.push_back(buf);
        }
        sort(input.begin(), input.end());
 
        TrieNode* trie = new TrieNode();
        bool check = false;
        for (int i = 0; i < input.size(); i++) {
            TrieNode* node = trie->find(input[input.size() - 1 - i].c_str());
            if (node != NULL) check = true;
            trie->insert(input[input.size() - 1 - i].c_str());
        }
        if (check) cout << "NO\n";
        else cout << "YES\n";
    }
}

 

 

개발환경 : Visual Studio 2019

지적, 조언 언제든지 환영입니다~~