[BOJ] C++ 5052 전화번호 목록 - 문자열과 정렬

5052번: 전화번호 목록

예제

2
3
911
97625999
91125426
5
113
12340
123440
12345
98346

ans :
NO
YES

---

한 번호가 다른 번호의 접두어인 경우가 있는지 체크하는 문제이다. 예를 들어 911과 9112314에서 911은 9112314의 접두어이므로 일관성이 없다고 판단한다. 

 

1. 가장 간단하게 생각할 수 있는 방법으로 첫 문자열부터 끝까지 다 비교하는 방법을 생각했다. 시간제한은 1초이고 전화번호가 최대 10000개, 10자리이므로 10000^2 * 10^2 만큼 비교해야 하므로 당연히 시간초과가 뜰 것이다.

 

2. 기수 정렬 느낌으로 자리수별로 정렬해서 판단해 나가는 방법을 생각했다. 그리고 매 단계마다 각 자릿수 별 칸에 담긴 게 자기 혼자 뿐이라면 일관성 있는 문자열이므로 삭제하는 방식으로 시간을 줄일 수 있다. 시간초과가 뜰지 안 뜰지 애매해서 일단 구현은 안 하고 보류했다.

 

3. 일관성 있는 문자열들끼리 모여있으므로 일단 정렬을 해보았다. 정렬하고 깨달은 중요한 포인트가 일관성 없는 문자열은 모여있다는 것이다. 즉, 사전순으로 리스트를 정렬했을 때 어떤 문자열 A의 다음 문자열이 일관성 있는데 그 다음 문자열이 A 때문에 일관성이 깨지는 일은 일어날 수 없다는 것이다. A문자열 다음 문자열이 A 때문에 일관성이 깨져야만 A 문자열 다음다음 문자열의 일관성이 A 때문에 깨질 가능성이 존재한다. 따라서 사전순으로 리스트를 정렬하고 각 문자열별로 다음 문자열만 체크하면 된다.

list[i] == list[i + 1].substr(0, list[i].length())

이런 식으로 말이다.

/**  **/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        vector<string> list(n);
        for (auto &x : list)
            cin >> x;
        sort(list.begin(), list.end());

        bool flag = true;
        for (int i = 0; i < n - 1; i++)
        { // list[n-1]은 마지막 원소이므로 확인할 필요가 없다.
            if (list[i] == list[i + 1].substr(0, list[i].length()))
            {
                flag = false;
                break;
            }
        }
        if (flag)
            cout << "YES\n";
        else
            cout << "NO\n";
    }
}