백준온라인 5052번 [전화번호 목록][C++]

www.acmicpc.net/problem/5052

5052번: 전화번호 목록

---

나의 풀이

처음에는 set으로 풀어도 TLE를 당하지 않으리라는 생각으로 제출했지만 시간 초과가 났었다...

트라이로 풀어야 겠다는 생각을 했지만 트라이를 무조건? 써야 될 것 같진 않아서 생각을 하다 보니 힌트를 얻었다.

 

만약 전화번호 목록이 

139

2321

12323

1392

다음과 같이 구성이 되어있다고 생각하면

 

문자열 전체를 보지 말고 모든 문자열을 사전순으로 정렬을 해보면

 

139

1392

12323

2321

 

다음과 같이 나오게 된다.

 

139와 1392는 NO를 판별하는 key가 되는데 이렇게 사전 순으로 정렬을 했는데

뒤의 문자열이 앞의 문자열보다 길이가 긴 경우 ,  짧은 문자열이 겹치는지 아닌지 판별을 해주어야 된다.

 

정리를 하자면

 

모든 문자열에 대해서 

사전순으로 정렬을 해주고 , 사전 순으로 같을 경우 길이가 증가하는 순서로 정렬해준다.

만약 문제에서 언급한 "겹치는 상황" 이 존재한다면 정렬이 끝난후 무조건 인접하여 존재할 것이다.

앞에서부터 순회를 하며

뒤의 문자열이 앞의 문자열보다 길지 않은 경우는 확인하지 판별하지 말고

(123,124,125 (길이가 같은 경우 )와 같은 경우이거나 23456 ,312 (앞의 것이 더 긴 경우)와 같은 경우)

두 문자열 중 문자 열중 길이가 짧은 문자열 까지는 매칭이 되는 경우에만  "NO"인 경우로 판단하여 주면 된다.

 

코드

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
using vs = vector<string>;

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

   int t;
   cin>>t;
   while(t--){
       int n;
       cin>>n;
       vs ss;
       string s;

       for(int i=0;i<n;i++){
           cin>>s;
           ss.push_back(s);
       }

       sort(all(ss));
       
       bool flag=true;
       for(int i=1;i<n;i++){
           if(ss[i-1].length()>=ss[i].length()){
               continue;
           }else{
               if(ss[i].substr(0,ss[i-1].length())==ss[i-1]){
                   flag=false;
                   break;
               }
           }
       }
       cout<<(flag?"YES":"NO")<<"\n";
   }
}