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

---

🔗 문제 링크

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

5052번: 전화번호 목록

---

💡 문제 접근

가장 먼저 접두사를 어떤 순서로 검사할지 정해야 하는데, 여기서 문제는 이 기준을 어떻게 정할 것인지다. 일단, 최소한 길이가 긴 전화번호가 짧은 전화번호의 접두사가 될 일은 없는데, 이런 방식으로 풀면 뒤의 모든 전화번호들을 검사해야 되기 때문에, 시간초과가 났다. 여기서 정렬을 하면서 힌트를 얻은 것이 있는데, string을 정렬하면 [123,234,13,12999] 가 있다면, [123,12999,13,234] 순으로 정렬된다는 것이다. 여기서 123 -> 12999 일 때, 맨 앞자리 -> 그 다음자리 이런 순으로 정렬된다는 것을 알 수 있는데, 이러면 자연스럽게 0123456789 순으로 나열이 된다. 따라서 현재의 전화번호와 그 뒤의 전화번호만 비교해줘도 모든 접두사를 비교할 수 있는 것이다.

---

💡 문제 풀이 및 해석

1. 모든 전화번호를 string으로 받은 다음에 오름차순으로 정렬한다.
2. 정렬된 전화번호들을 "현재 전화번호"와 "다음 전화번호"로 비교한다.
3. 현재 전화번호의 길이가 다음 전화번호의 길이보다 크거나 같으면, 비교할 필요가 없다.
   ex) cur = 12345, next = 124 이면, 어차피 번호가 3에서 4로 넘어가기 때문에, 접두사가 될 수 없다. 그리고 같은 번호는 없으니 cur = 123, next = 123인 경우도 없다.
4. next 전화번호를 cur 전화번호의 길이만큼 잘라서 접두사인지 비교해보고 같다면, NO를 출력하고 비교를 멈춘다.
5. 모든 비교를 해도 접두사가 없다면 YES를 출력한다.

---

⭐️ 정답 코드 및 설명

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

int n, t;

vector<string> init() {
    cin >> n;
    vector<string> numberBook(n);
    for (int i = 0; i < n; i++) {
        cin >> numberBook[i];
    }
    sort(numberBook.begin(), numberBook.end());
    return numberBook;
}

void sol(vector<string> numBook) {

    for (int i = 0; i < n - 1; i++) {
        string cur = numBook[i];
        string next = numBook[i + 1];

        if (cur.size() >= next.size()) continue;
        if (cur == next.substr(0, cur.size())) {
            cout << "NO" << endl;
            return;
        }
    }
    cout << "YES" << endl;
}

int main() {
    ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);

    cin >> t;
    for (int testcase = 0; testcase < t; testcase++) {
        vector<string> numberBook = init();
        sol(numberBook);
    }

    return 0;
}

---

🤔 문제 후기

전화번호의 길이와 상관있을 줄 알았던 문제였다. 처음에는 길이가 긴 전화번호를 먼저 넣고, 현재의 길이보다 작은 전화번호가 들어오면 지금까지 들어온 전화번호들을 모두 체크하는 방식을 했는데, 10%에서 시간초과로 문제를 틀렸다. 그리고 숫자 처음에 0이 들어오면 생략되는데 그 점을 간과하여 풀었다가 어떤 문제인지 몰랐다. 결과적으로 우연하게 string으로 받은 다음에 정렬하여 출력해봤는데, 풀이가 보인 뒤로는 쉽게 푼 문제였다.