[백준] 5052번 전화번호 목록 (C++)

문제

전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오.

전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다.

예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자

• 긴급전화: 911
• 상근: 97 625 999
• 선영: 91 12 54 26

이 경우에 선영이에게 전화를 걸 수 있는 방법이 없다. 전화기를 들고 91을 누르는 순간 바로 긴급전화가 걸리기 때문이다. 따라서, 이 목록은 일관성이 없는 목록이다.

입력

첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 하나씩 주어진다. 전화번호의 길이는 길어야 10자리이며, 목록에 있는 두 전화번호가 같은 경우는 없다.

예제 입력 1

2
3
911
97625999
91125426
5
113
12340
123440
12345
98346

출력

각 테스트 케이스에 대해서, 일관성 있는 목록인 경우에는 YES, 아닌 경우에는 NO를 출력한다.

예제 출력 1

NO
YES

풀이

문제 해결 방법

이 문제는 트라이(Trie) 자료구조를 사용하여 해결할 수 있습니다. 주요 해결 단계는 다음과 같습니다:

1. 트라이 구현: 문자열을 저장할 트라이 자료구조를 구현합니다.
2. 문자열 삽입: 각 전화번호를 트라이에 삽입합니다.
3. 접두어 확인: 삽입 과정에서 현재 번호가 다른 번호의 접두어가 되는지 확인합니다.
4. 결과 판단: 모든 번호가 문제없이 삽입되면 YES, 아니면 NO를 출력합니다.

이 알고리즘의 시간 복잡도는 O(N × L)입니다. 여기서 N은 전화번호의 수, L은 전화번호의 최대 길이입니다.

코드

#include<stdio.h>

struct Trie{
    bool check;
    Trie* tr[10];

    Trie(){
        check=false;
        for(int i=0;i<10;i++)
            tr[i] = nullptr;
    }
    ~Trie(){
        for(int i=0;i<10;i++)
            if(tr[i]) delete tr[i];
    }
    bool insert(char *t){
        if(check==true) return false;
        if(!*(t))
        {
            check = true;
            for(int i=0;i<10;i++)
                if(tr[i]!=nullptr)
                    return false;
            return true;
        }
        if(tr[*t-'0']==nullptr)
            tr[*t-'0'] = new Trie();
        return tr[*t-'0']->insert(t+1);
    }
}*tr;

int n;
char phone[12];

int main()
{
    int t;
    scanf("%d",&t);

    for(int tt=1;tt<=t;tt++)
    {
        scanf("%d",&n);

        tr = new Trie();

        bool ans = true;
        for(int i=1;i<=n;i++)
        {
            scanf("%s",phone);
            if(ans){
                bool tf = tr->insert(phone);
                ans&=tf;
            }
        }

        delete tr;

        puts(ans?"YES":"NO");
    }
    return 0;
}