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

5052번: 전화번호 목록

해시 셋을 이용한 문제이다. 먼저 모든 입력을 벡터로 받아준 후 이를 오름차순으로 정렬을 해준다. 그리고 반복문을 돌며 해당 전화번호의 한글자 씩 tmp에 넣어보며 해시 셋에 있는 전화번호들과 비교하여 만약 존재할 경우 NO를 출력해주고 없다면 현재 전화번호를 해시 셋에 넣어준다. 반복문을 끝까지 완료하면 YES를 출력해주었다.
간단하게 풀 수 있었던 문제였다. 사실 해시 셋이 아니라 이진 트리 방식인 그냥 셋을 사용해도 통과를 한다. 이번 문제의 경우 케이스가 많지가 않기 때문에 해시 셋을 사용하는 것이 속도가 더 빠르기 때문에 해시 셋을 사용해주었다. 만약 케이스가 많다면 그냥 셋이 더 속도가 빠를 것이다. 그리고 트라이 알고리즘이란 방식으로도 이 문제를 풀 수 있었는데 처음보는 개념이라 많이 신기했다. 트라이 알고리즘에 대해서도 공부를 해봐야 겠다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>

using namespace std;

int n;
vector<string> v;
unordered_set<string> set;

void solution() {
    sort(v.begin(), v.end());

    for (int i = 0; i < n; i++) {
        string tmp = "";

        for (int j = 0; j < v[i].size() - 1; j++) {
            tmp += v[i][j];

            if (set.find(tmp) != set.end()) {
                cout << "NO\n";
                return;
            }
        }

        set.insert(v[i]);
    }

    cout << "YES\n";
}

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

    int t;
    cin >> t;

    while (t--) {
        v.clear();
        set.clear();

        cin >> n;

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

        solution();
    }

    return 0;
}