[Gold 4] 5052 전화번호 목록

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

5052번: 전화번호 목록

 

 

트리이를 공부하다 찾은 문제이다.

트라이는 문자열을 효율적으로 탐색할 수 있는 자료구조이다.

 

문제에서 전화번호 목록이 아래와 같이 주어진 경우

긴급전화: 911

상근: 97 625 999

선영: 91 12 54 26

선영의 전화번호를 입력할 경우 입력 중 긴급전화로 연결되어 일관성이 없는 목록이 된다.

 

따라서 전화번호를 입력 받고 각 전화번호가 연관성이 있는지 검사하면 된다.

 

알고리즘은 다음과 같다.

1. 문자열을 입력 받고 배열에 저장한다.
2. 배열을 정렬한다.
   • 이는 전화번호를 오름차순으로 정렬하여 "625"와 "62581"이 입력된 경우 "625"를 앞으로 오게하여 "62581"의 접두어인 "625"를 찾기 위해 하는 것이다.
3. 배열을 순회한다.
   • i번째 요소와 i+1번째 요소를 통해 검사를 시작한다.
   • i번째 요소의 문자열 길이가 더 긴 경우 무시 -> 접두어 검사를 할 수 없음
   • i+1 번째 요소를 i번째 요소의 길이만큼 자르고 같은지 검사 -> 같다면 일관성이 없는 목록

 

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


int T, N;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> T;
    for(int test_case = 0; test_case < T; test_case++){
        int n; cin >> n;
        string str;
        vector<string> v;
        
        for(int i = 0; i<n; i++){
            cin >> str;
            v.push_back(str);
        }

        sort(v.begin(), v.end());
        bool flag = true;
        for(int i = 0; i<v.size()-1; i++){
            string cur = v[i];
            string next = v[i+1];
            flag = true;
            if(cur.length() > next.length()) continue;
            if(cur == next.substr(0, cur.length())){
                flag = false;
                break;
            }
        }
        if(!flag) cout << "NO\n";
        else cout << "YES\n";
    }
 
    return 0;
}