전화번호 목록 //5052

• 문제
  전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오.
  전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다.
  예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자
  긴급전화: 911
  상근: 97 625 999
  선영: 91 12 54 26
  이 경우에 선영이에게 전화를 걸 수 있는 방법이 없다. 전화기를 들고 선영이 번호의 처음 세 자리를 누르는 순간 바로 긴급전화가 걸리기 때문이다. 따라서, 이 목록은 일관성이 없는 목록이다.
  
  //시간 제한: 1초, 메모리 제한: 256MB

• 입력
  첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 하나씩 주어진다. 전화번호의 길이는 길어야 10자리이며, 목록에 있는 두 전화번호가 같은 경우는 없다.

• 출력
  각 테스트 케이스에 대해서, 일관성 있는 목록인 경우에는 YES, 아닌 경우에는 NO를 출력한다.

// Created by dongwan-kim on 2022/07/26.
#include<iostream>
#include<queue>
#include<string>

using namespace std;


int t, n;
string f, s;
bool ans;

int main() {
    cin >> t;
    while (t--) {
        priority_queue<string, vector<string>, greater<>> pq;
        ans = true;
        cin >> n;
        for (int i = 0; i < n; i++) {
            cin >> s;
            pq.push(s);
        }

        for (int i = 0; i < n; i++) {
            s = pq.top();
            pq.pop();
            if (!pq.empty() && pq.top().substr(0, s.length()) == s) {
                ans = false;
                break;
            }
        }

        if (ans)
            cout << "YES" << '\n';
        else
            cout << "NO" << '\n';

    }
}

풀이

pq를 사용하여 문제를 해결했다
문자열을 오름 차순으로 정렬해 주면 만약 한 번호가 다른 번호의 접두어인 경우라면 붙어있게 될 것이다.
이 부분을 이용하여 priority queue에 입력을 넣어주고 n번 반복문을 돌면서 자신과 자신 뒤에있는 문자열을 비교해서 접두어가 같은지 다른지 판별하였다.
문자열의 길이는 정렬했을 때 같은 접두어를 갖고있다면 짧은 문자열이 더 앞에 있을 것이므로
뒤에 있는 문자열을 앞에 있는 문자열의 길이만큼 subst해서 비교하였다.
마지막엔 bool타입 ans에 따라 정답을 출력하였다.

맨처음 문제를 접근 할때는 벡터배열을 크기 10만큼 선언해서 입력받은 문자열 s의 첫번째 문자에 따라 분류하여 벡터배열에 넣어주는 식으로 구현했었다.
하지만 구현을 하다보니 시간 초과가 난다는 것을 알고 코드를 한번 엎었었다.