[BOJ 5052] 전화번호 목록

5052번: 전화번호 목록

문제 분석

• 시간 제한 : 1초
• 다뤄야 하는 전화번호의 개수 :  10,000
• 테스트 케이스 : 50
• 어떤 값이 다른 값의 substring인지를 파악하는 문제

풀이 방식

• 문자열로 입력받은 전화번호를 사전순으로 정렬 ⇒ (1,2,3...,999,1000)X, (1,10,100,1000,11,111,112...)O
• 첫번째부터 다음꺼랑 비교
• 어떤 값이 다른 값의 substring이라면 두 값은 붙어있을 수 밖에 없다. 

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

using namespace std;

int t,n;
string num;
bool possible;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>t;
    while(t--){
        cin>>n;
        possible = true;
        vector<string>pb;
        //clear시간을 줄이기 위해 테스트 케이스 안에서 벡터선언(PhoneBook)
        while(n--){
            cin>>num;
            pb.push_back(num);//벡터에 입력
        }
        sort(pb.begin(), pb.end());//사전순으로 정렬
        for(int i=1;i<pb.size();i++){
            if(pb[i-1]==pb[i].substr(0,pb[i-1].size())){//substr이 발견되면
                cout<<"NO"<<"\n";//NO 출력하고
                possible = false;
                break;//반복문 정지
            }
        }
        if(possible) cout<<"YES"<<"\n";
        //NO 출력한적 없으면 substr 발견된적 없는 것
    }
    return 0;
}

느낀 점

• 처음에는 <map>을 사용하면 풀 수 있을 거란 생각에 key를 어떤값으로 할까 이런 고민을 했다.
• 도저히 떠오르지 않아 다른 방법이 없을 까 하는 생각을 했고, 사전순으로 정렬되어 있으면 문제해결이 쉬어지겠다는 생각을 했다.
  사전순으로 정렬하면 된다는 생각이 문제를 해결하는데에 결정적이었고, 이런 생각을 해내 뿌듯했다.
• 문제를 풀고나서 <priority_queue>와 같이 저장할때 부터 저장하는 게 효율적일 수 도 있겠다는 생각이 들었으나 좀더 고민해보니, 새로운 값을 push할때나 맨앞의 값을 pop할때나 그때 그때 정렬해줘야 한다는 생각에 <vector>를 쓴 방법이 효과적이었겠다는 생각이 들었다.

시간복잡도 (1 테스트 케이스 기준)

• while문 n번 반복 ⇒ O(n)
• 사전순 정렬 ⇒ O(nlogn) 기대
• for문 벡터 크기 만큼 반복 ⇒ O(n)
• 비교 연산 ⇒ O(1)
  ☞ O(nlogn)