백준 5052 - 전화번호 목록

문제 설명

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

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

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

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

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

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, 전화번호가 주어졌을 때 하나의 전화번호가 다른 전화번호의 접두어인지 확인하는 문제이다.

 

문제를 읽어보면 바로 트라이 문제라는 것을 알 수 있다.

하지만, 전형적인 트라이 구조를 만들려고 하다 보니 특정 전화번호가 언제 끝나는지 체크하는 것이 쉽지 않았다.

또한, 이를 구현하는 것부터 까다롭다.

 

이를 해결하는 것은 간단했다.

특정 정렬기준이 있을 때 자신의 접두어가 있는지 확인해 나가면 된다.

정렬기준은 길이순이 제일 적절한 것 같다.

 

접두어를 확인하는 과정은 하나의 전화번호를 한 자리씩 추가하며 이전 전화번호와 일치하는 것이 있는지 확인하는 것이다.

즉, string을 저장하는 hashSet이 있다면 해결된다.

unordered_set<string> hashSet;

for (int i = 0; i < N; i++)
{
    string prefix;

    for (int j = 0; j < strs[i].length(); j++)
    {
        prefix += strs[i][j];

        if (hashSet.count(prefix) != 0)
        {
            flag = false;
            break;
        }

    }

    if (!flag) break;
    hashSet.insert(prefix);
}

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>
#include <unordered_set>
using namespace std;
#define INPUT_OPTIMIZE cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define INF 2e9

using namespace std;
int T, N;


int main() 
{
    INPUT_OPTIMIZE;

    cin >> T;

    while (T--)
    {
        cin >> N;

        bool flag = true;
        vector<string> strs;

        for (int i = 0; i < N; i++)
        {
            string str;
            cin >> str;

            strs.push_back(str);
        }

        sort(strs.begin(), strs.end());

        unordered_set<string> hashSet;

        for (int i = 0; i < N; i++)
        {
            string prefix;

            for (int j = 0; j < strs[i].length(); j++)
            {
                prefix += strs[i][j];

                if (hashSet.count(prefix) != 0)
                {
                    flag = false;
                    break;
                }

            }

            if (!flag) break;
            hashSet.insert(prefix);
        }

            
        if (flag)
        {
            cout << "YES\n";
        }
        else
        {
            cout << "NO\n";
        }
    }
    

    return 0;
}

---