백준) 5052 전화번호 목록

전화번호 목록

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

트라이 구조체의 10칸짜리 숫자 판을 보면서, 중간에 끝나는 문자열이 삽입되었는지를 기억해야 한다.

따라서 구조체에 끝났는지 기억하는 변수를 추가해줘서, 삽입함수가 끝날 때 해당 구조체에 기록해둔다.

이제 모든 전화번호들을 트라이들을 헤집으면서 탐색할 때, 아직 전화번호가 끝나지 않았는데, 끝났다는 기록이 나오면

일관성 없는 목록임을 알 수 있다.

#include <stdio.h>
#define num 10
#define maxn 10000
 
struct trie {
    trie* pan[num];
    bool end;
 
    trie() {
        for (int i = 0; i < num; ++i)
            pan[i] = nullptr;
        end = false;
    }
    ~trie() {
        for (int i = 0; i < num; ++i)
            if (pan[i] != nullptr)
                delete pan[i];
    }
 
    void insert(char* str) {
        if (*str == '\0') {
            end = true;
            return;
        }
        //종료
        int cur = *str - '0';
        if (pan[cur] == nullptr)
            pan[cur] = new trie();
        pan[cur]->insert(str + 1);
    }
 
    int find(char* str) {
        if (*str == '\0')
            return 0;
 
        if (end)
            return 1;
 
        int cur = *str - '0';
        return pan[cur]->find(str + 1);
    }
};
 
int t, n;
char buf[maxn][11];
 
int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
 
        trie* root = new trie();
 
        for (int i = 0; i < n; ++i) {
            scanf("%s", buf[i]);
            root->insert(buf[i]);
        }
        
        bool ans = true;
        for (int i = 0; i < n; ++i) {
            if (root->find(buf[i])) {
                ans = false;
                break;
            }
        }
        if (ans)
            puts("YES");
        else
            puts("NO");
 
        delete root;
    }
}