백준(BOJ)_전화번호 목록(5052번)_C++

구현자체는 쉬웠는데 그 구현을 생각해내기가 조금 걸렸다.

 

처음엔 단순히 숫자라 생각해서 long long형으로 전화번호를 입력받았는데

생각해보니 0으로 시작하는 전화번호도 있을거라 생각해서 string으로 입력받았다.

(최대 10자리이기 때문에 int형보다 큰 숫자가 가능해서 처음에 long long형으로 선택했다.)

 

그리고 각 문자열들끼리 비교를 해야하는데 처음엔 모든 문자열끼리 비교했고,

당연히 시간초과가 나왔다.

최악의 경우 문자열을 비교하는 데에만 10,000*10,000=100,000,000번 비교해야하기 때문에 시간초과는 당연했다.

 

그래서 조금 고민하다가 정렬된 벡터를 출력해보면서 해결할 수 있었다.

 

string으로 입력받으면 벡터를 정렬했을 때 숫자의 크기가 아니라

문자열의 크기순으로 정렬되기 때문에 가장 비슷한 숫자끼리 모여있게 된다.

그래서 모든 문자열끼리 비교할 필요없이 인접한 인덱스의 문자열끼리만 비교하면 됐다.

 

이렇게 해서 기준문자열의 길이가 비교하려는 문자열의 길이보다 작거나 같을 때

기준문자열과 비교하려는 문자열의 접두어가 같으면 NO를 출력한다.

 

나도 이 생각이 한 번에 떠오르진 않았고, 정렬된 벡터의 출력을 보면서 고민해보다가 나왔다.

문자열의 정렬과 숫자의 정렬의 차이점을 인지하는 것이 이 문제의 키포인트라고 생각한다.

 

 

풀고나서 알고리즘 분류를 보니 트라이라는 자료구조를 이용해서 푸는 방법도 있었다.

그런데 C++에서 트라이를 사용하려면 직접 구현해서 사용해야하는 것 같아서 더 공부해서 풀어보기로 했다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

int t, n;
vector<string> v; //10자리 or 0으로 시작

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

    cin >> t;
    while(t--){
        cin >> n;
        v.clear();
        string temp;
        for(int i=0; i<n; i++){
            cin >> temp;
            v.push_back(temp);
        }
        
        sort(v.begin(), v.end());
        
        bool flag=true;
        for(int i=0; i<v.size()-1; i++){
            if(v[i].length()<=v[i+1].length()){
                if(v[i]==v[i+1].substr(0, v[i].size())){
                    flag=false;
                    break;
                }
            }
        }

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