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

문제

백준 5052 전화번호 목록 C++

5052번: 전화번호 목록

풀이

트라이나 정렬을 이용합니다

1) 정렬로 풀이

1. 문자열을 모두 입력 받은 후 오름차순 정렬합니다.

-> 문자열 순서가 작은 것이 앞으로 오고, 순서가 같다면 string 길이가 더 작은 것이 앞으로 옵니다.

2. i번째 문자열이 i+1문자열의 앞과 똑같다면 일관성이 없으므로 루프를 중단하고 NO를 출력합니다.

3. N-1번째 문자열까지 똑같지 않다면 일관성이 있으므로 YES를 출력합니다.

소스 코드

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        int N;
        cin >> N;
        vector<string> v;
        for (int i = 0; i < N; i++)
        {
            string str;
            cin >> str;
            v.push_back(str);
        }
        sort(v.begin(), v.end());
        bool coherent = true;
        for (int i = 0; i < v.size() - 1; i++)
        {
            if (v[i] == v[i + 1].substr(0, v[i].length())) {
                coherent = false;
                break;
            }
        }
        // 일관성이 있으면
        if (coherent) {
            cout << "YES" << '\n';
        }
        else {
            cout << "NO" << '\n';
        }
    }
    return 0;
}