[BOJ] 5052 전화번호목록 C++

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

5052번: 전화번호 목록

트리라고 적혀있어서 들어갔는데 그리디가 먼저 보여서 그리디로 풀었다. C++의 STL을 활용하면 아주 쉽게 풀 수 있는 문제이다.

 

전화번호가

12345

12

1589

98

159 

이렇게 주어졌다고 하자. string으로 값을 받고 배열 arr에 저장 후 sort를 해주면 사전 순으로 sort를 해주는데 그럼

12

12345

1589

159

98

이렇게 sort가 된다. 여기서 arr[i-1].size()>arr[i].size()면 무조건 조건을 만족하는 경우이므로 비교 할 필요가 없다. 

arr[i-1].size()<=arr[i].size()일 경우 배열을 비교하면서 모두 같은 경우가 있으면 "NO"를 출력해주면 된다.

 

코드

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

int T,N;

int main(){
    cin>>T;
    while(T--){
        cin>>N;
        string s;
        vector<string> v;
        for(int i=0;i<N;i++){
            cin>>s;
            v.push_back(s);
        }
        bool flag;
        sort(v.begin(),v.end());
        for(int i=1;i<N;i++){
            string s1=v[i-1];
            string s2=v[i];
            flag=false;
            if(s1.size()<=s2.size()){
                flag=true;
                for(int j=0;j<s1.size();j++){
                    if(s1[j]!=s2[j]){
                        flag=false;
                        break;
                    }
                }
            }
            if(flag){
                cout<<"NO"<<'\n';
                break;
            }
        }
        if(!flag) cout<<"YES"<<'\n';
    }
    return 0;
}