백준[5052] 전화번호 목록

문제 설명

문제 링크

http://icpc.me/5052

5052번: 전화번호 목록

풀이

트라이를 이용하여 풀 수 있다.

트라이에 전화번호를 넣는 과정에서 prefix가 똑같은 문자열을 발견하면 NO를 출력하면 된다.

cf) new Trie()를 하여 동적 할당을 하는 것보다 전역 변수로 Trie를 많이 만들어 할당해주는 방식이 더 빠르기 때문에 아래와 같이 구현했다.

코드

#include <cstdio>

struct Trie;
Trie* new_trie();

struct Trie {
    int child;
    bool finish;
    Trie *nxt[11];

    bool insert(const char *key) {
        if (*key == 0) {
            finish = true;
            return child ? false : true;
        }
        if (finish) return false;
        child++;
        int idx = *key - '0';
        if (!nxt[idx]) nxt[idx] = new_trie();
        return nxt[idx] -> insert(key + 1);
    }
};

Trie arr[2000006];
int cnt;

Trie* new_trie() {
    return &arr[cnt++];
}

void solve() {
    int n; scanf("%d", &n);
    Trie *root = new_trie();
    bool flag = true;
    while (n--) {
        char s[12]; scanf("%s", s);
        if (!(root -> insert(s))) flag = false; 
    }
    printf("%s\n", flag ? "YES" : "NO");
}

int main() {
    int t; scanf("%d", &t);
    while (t--) solve();
}