[백준 / BOJ] 5052 전화번호 목록

분류: 문자열, 트라이(Trie), 정렬, 해시맵

문제: www.acmicpc.net/problem/5052

5052번: 전화번호 목록

• 3가지 방법으로 풀어본 문제이다.
• 정렬을 사용한 방식이 가장 효율성이 높았다.

---

1. 정렬

#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <iostream>
#include <climits>
#include <cstring>
#include <iomanip>
#include <bitset>
#include <string>
#include <vector>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>

#define ll long long
#define INF 1e9

using namespace std;

//https://www.acmicpc.net/problem/5052 전화번호 목록

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

    int t, n;
    cin >> t;
    while(t--) {
        cin >> n;
        string s[10001] = {};
        for(int i=0; i<n; i++) {
            cin >> s[i];
        }
        sort(s, s+n);
        int flag = 0;
        for(int i=1; i<n; i++) {
            if(s[i].substr(0, s[i-1].size()) == s[i-1]) {
                flag = 1;
                break;
            }
        }
        if(flag) cout << "NO";
        else cout << "YES";
        cout << '\n';
    }

    return 0;
}

---

2. 해시맵

#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <iostream>
#include <climits>
#include <cstring>
#include <iomanip>
#include <bitset>
#include <string>
#include <vector>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>

#define ll long long
#define INF 1e9

using namespace std;

//https://www.acmicpc.net/problem/5052 전화번호 목록

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

    int t, n;
    cin >> t;
    while(t--) {
        cin >> n;
        string s[10001] = {};
        unordered_map<string, int> m;
        for(int i=0; i<n; i++) {
            cin >> s[i];
            m[s[i]] = 1;
        }
        int flag = 0;
        for(int i=0; i<n; i++) {
            string tmp = "";
            for(char c: s[i]) {
                tmp += c;
                if(tmp != s[i] && m[tmp] == 1) {
                    flag = 1;
                    break;
                }
            }
            if(flag) break;
        }
        if(flag) cout << "NO";
        else cout << "YES";
        cout << '\n';
    }

    return 0;
}

---

3. 트라이(Trie)

#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <iostream>
#include <climits>
#include <cstring>
#include <iomanip>
#include <bitset>
#include <string>
#include <vector>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>

#define ll long long
#define INF 1e9

using namespace std;

//https://www.acmicpc.net/problem/5052 전화번호 목록

struct Trie {
    Trie* next[10];
    bool finish;
    bool next_child;
    
    Trie() {
        finish = next_child = false;
        memset(next, 0, sizeof(next));
    }
    
    ~Trie() {
        for(int i=0; i<10; i++) {
            if(next[i]) delete next[i];
        }
    }
    
    // 문자열 key를 현재 노드부터 삽입 후 일관성 여부를 반환
    bool insert(const char* key) {
        if(*key == 0) {
            finish = true;
            if(next_child) return false;
            else return true;
        }
        if(finish) return false;
        int cur = *key - '0';
        if(next[cur] == NULL) next[cur] = new Trie();
        next_child = true;
        return next[cur]->insert(key + 1);
    }
};

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int t, n;
    cin >> t;
    while(t--) {
        cin >> n;
        Trie* root = new Trie;
        int flag = 0;
        char phone[11] = {};
        for(int i=0; i<n; i++) {
            cin >> phone;
            if(flag == 0 && root->insert(phone) == 0) flag = 1;
        }
        if(flag) cout << "NO";
        else cout << "YES";
        cout << '\n';
        delete root;
    }
    
    return 0;
}