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

📕문제

---

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

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

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

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

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

📕입력

---

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

📕출력

---

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

 

🔎문제 해석

---

일관성 있는 번호란 접두어가 겹치지 않는 것이다.

그럼 접두어의 의미란 무엇일까요?

전화번호를 길이 순으로 정렬한 뒤 바로 직전의 전화번호의 길이가 접두어가 될 것입니다.

예를 들어 생각해봅시다.

123
1234
12345

 

이렇게 번호 목록이 있다면 123을 누를 경우 1234와 일관성이 없고, 1234를 누를 경우 12345와 일관성이 없어집니다.     

즉 바로 직전의 길이의 전화번호와 같은 내용의 전화번호가 있으면 안 됩니다.

만약 하나라도 이 일관성을 어긴다면 그 전화번호 목록은 일관성이 없어집니다.

그럼 우리는 이제 전화번호 목록을 입력받고 전화번호의 길이를 기준으로 오름차순으로 정렬한 뒤 직전의 전화번호의 길이만큼 전화번호가 일치하는지 검사를 해 주면 됩니다.

[다 풀고 구글링 하니 substr이라는 알고리즘이 있던데 그거를 쓸걸 이라고 후회가 되네요.]

 만약 일관성이 없는 번호가 있다면 그 즉시 검사를 멈춰줍니다. 한 번도 검사가 멈춰지지 않았다면 그 전화번호 목록은 일관성이 있겠죠~~~~?!

💻코드

/*
백준 골드4 전화번호 목록
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <string>

using namespace std;
int t, n;
bool comp(vector<string> a, vector<string> b)
{
    return a.size() > b.size();
}
vector<string> phone;
vector<string> ans;
int main()
{
    cin >> t;
    for (int x = 0; x < t; x++)
    {
        cin >> n;
        bool flag = true;
        for (int i = 0; i < n; i++)
        {
            string str;
            cin >> str;
            phone.push_back(str);
        }
        sort(phone.begin(), phone.end()); //번호의 길이를 기준으로 오름차순으로 번호를 정렬한다.
        int p = 0;
        for (int k = 0; k < phone.size() - 1; k++)
        {
            int count = 0;
            for (int j = 0; j < phone[k].size(); j++)
            {
                if (phone[k][j] == phone[k + 1][j])
                {
                    count++;
                }
            }
            if (count == phone[k].size()) //접두어의 길이와 count가 값다면 그 번호는 일관성이 없다.
            {
                cout << "NO" << endl;
                break;
            }
            p++; //일관성이 없는 번호라면 하나씩 더해준다.
        }
        if (p == phone.size() - 1) // p의 값과 비교횟수와 같다면 그건 일관성 있는 번호들만 있기에 yes를 출력
        {
            cout << "YES" << endl;
        }
        phone.clear();
    }
}

 

✔느낀 점

• 라이브러리의 소중함을 알았습니다.
• 굉장히 멍청한 알고리즘을 짠 저 자신에게 반성을 합니다.