[BOJ] 백준 5052 전화번호 목록

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

 Input 

2

3

911

97625999

91125426

5

113

12340

123440

12345

98346

 

 Output 

NO

YES

접두사를 이용해서 전화번호를 누르기 전에 다른 전화로 걸리는지 확인.

(일상에서의 [통화 연결] 버튼이 따로 존재하지 않는다고 보면 됩니다.)

 

▶ Trie 이용

: Trie 자료구조에 번호들을 추가하면서 현재 주어진 번호가 다른 번호의 접두어가 되는지 바로 판단

※ 숫자로 된 문자열이므로 10진 트리로 이해할 수도 있습니다.

 

---

#include <iostream>
#include <cstring>
using namespace std;
 
int charToIndex(char c){
    return c - '0';
}
 
struct Trie {
 
    bool isTerminal;
    Trie * next[10];
 
    Trie() : isTerminal(false) {
        memset(next, 0, sizeof(next));
    }
 
    ~Trie() {
        for (int i = 0; i < 10; ++i) {
            if (next[i]) {
                delete next[i];
            }
        }
    }
 
    bool insert(const char * key) {
        if (*key == '\0') {
            isTerminal = true;
            return true;
        }
        else {
            
            if(isTerminal == true) return false;
 
            int index = charToIndex(*key);
            if (next[index] == 0)
                next[index] = new Trie();
 
            else if(next[index] != 0 && *(key + 1) == '\0'){
                return false;
            }
            return next[index]->insert(key + 1);
        }
    }
};
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    int TC, N; cin >> TC;
    char phoneBook[10000][11];
 
    while (TC--) {
        cin >> N;
        
        Trie * root = new Trie();
        bool answer = true;
        for (int i = 0; i < N; ++i) {
            cin >> phoneBook[i];
            if (answer == false) continue;
            answer = root->insert(phoneBook[i]);
        }
        delete root;
 
        printf("%s\n", answer ? "YES" : "NO");
    }
}