[백준 5052][💛4] 전화번호 목록 (해시, 트라이)

🚀 난이도

💛 골드 4

🚀 문제

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

🚀 내 풀이

프로그래머스의 “전화번호 목록” 문제와 똑같다. 심지어 문제 이름도 똑같네! 입력 크기는 프로그래머스 문제가 더 빡센 편이다.

🔥 해시 사용한 풀이

• 1️⃣ 현재 검사하는 번호의 접두어들이 해시셋에 있는지 검사. 있다면 “NO” 출력 후 종료
  • “abcd” 라는 단어가 있다면 “a”, “ab”, “abc” 가 접두어 (문제에서 같은 단어가 주어지는 경우는 없다고 했으니 “abcd”는 해당 안됨)
  • 모든 번호들이 전부 이 검사를 통과했다면 “YES” 출력
• 2️⃣ 현재 검사하는 번호의 모든 접두어가 해시셋에 없었다면 해시셋에 현재 번호를 추가 (다른 번호의 접두어가 될 수 있으니)

문자열 배열을 미리 정렬 해둔 후 위 과정을 수행해야 한다. 정렬을 하면 625 는 62581 보다 앞에 오게된다. 그러면 62581 에서 접두어 625 를 찾아낼 수 있다. 만약 정렬이 되어 있지 않아 62581 이 625 보다 앞에 있다면 62581 에 625 접두어가 있음에도 불구하고 625 가 해시셋에 추가되기 전에 검사가 이루어졌기 때문에(즉 이 시점에선 625 를 모르는 상태) 찾아내지 못하게 된다.

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t, n;
    cin >> t;
    
    for (int i = 0; i < t; ++i) {
        cin >> n;
        vector<string> arr(n);
        for (int j = 0; j < n; ++j)
            cin >> arr[j];
        
        sort(arr.begin(), arr.end()); // 정렬
        unordered_set<string> hash_set;
        bool flag = false;
        for (int j = 0; j < n; ++j) {
            string str = ""; // arr[j]의 접두어
            for (int k = 0; k < arr[j].length() - 1; ++k) { //문제에서 같은 단어가 주어지는 경우는 없다고 했기 때문에 lengh() - 1
                str += arr[j][k]; // 접두어 만들기
                if (hash_set.find(str) != hash_set.end()) {
                    flag = true;
                    cout << "NO" << '\n';
                    break;
                }
            }
            if (flag) break;
            hash_set.insert(arr[j]); // 현재 단어 추가
        }
        if (!flag) cout << "YES" << '\n';
    }
}

🔥 트라이 자료구조 사용한 풀이

트라이에 관한 더 자세한 설명은 이 포스트를 참고해주세요. 👉 (C++) 문자열 집합 : 트라이 자료구조

문자열들이 저장되어 있는 트라이 트리(Trie tree)에서 단어의 첫 글자부터 타고 내려오며 검사를 하기 때문에 접두어 를 찾기에 좋은 자료구조이다. 단어들은 루트부터 트리형태로 한 데 모여있기 때문이다. 자연스럽게 루트부터 타고 내려오면 모든 단어의 첫 문자부터 검사하는게 되기 때문에 접두어 찾기에 딱이다.

• 먼저 트라이 트리를 만들고 전화번호 문자열들을 모두 저장한다.
• 1️⃣ 현재 검사하는 번호가 트라이 트리에서 자기 자신(현재 검사하는 번호의 끝)을 제외하고 어떤 단어의 끝에 도달하였는지를 검사. 있다면 “NO” 출력 후 종료
• 2️⃣ 현재 검사하는 번호가 트라이 트리에서 자기 자신의 끝(현재 검사하는 번호의 끝)까지 내려와 버릴 동안 “끝 단어”를 만나지 못했다면 “YES” 출력 후 종료

트라이(Trie) 트리에 { 911, 9732, 91125, 265 } 문자열들을 넣어주면 위와 같은 모습이 된다. (자식 노드 링크를 0~9 배열에 저장하여서 위와 같은 그림으로 표현함!) 문자열마다 끝이 표시되어있다.

91125 같은 문자열은 쭉쭉 내려오다가 911 까지 왔을 때 isEnd 가 True 인 상태를 맞닥뜨리게 된다. 911 이라는 단어도 존재하기 때문이다! 91125 는 본인의 끝이 아닌 중간에 isEnd 를 만났기 때문에 91125 접두어로 쓰인 단어가 있다는 의미가 된다. 따라서 이와 같은 경우엔 접두어가 존재하는 경우이다.

마찬가지로 문자열들을 정렬해준 후 위 과정을 실행해야 한다.

#include <bits/stdc++.h>

using namespace std;

class Trie {
private :
    bool isEnd = false;  // 이 Trie 노드 객체가 문자열(단어)의 끝인지를 알 수 있는
    Trie* child[10]; // Trie 객체들은 각각 서브 트리들의 루트 노드가 된다. 자식 10 개( 0 ~ 9 )를 담을 수 있는 배열을 가지고 있음 (배열말고 해시로 해도 된다.)
    
public :
    Trie() : child() { }
    
    /* 트라이 트리 만들기 */
    void Insert(string phone_number) {
        Trie* now = this; // 루트에서부터 시작 (루트 Trie 객체에서만 이 Insert 를 한번 실행하도록 함. 재귀 안 쓰고 반복문 써서..)
        for (int i = 0; i < phone_number.length(); ++i) {
            if (now->child[phone_number[i] - '0'] == nullptr) 
                now->child[phone_number[i] - '0'] = new Trie(); // 해당 글자 자식이 없다면 Trie 객체 만들어주기. 이미 있다면 만들어줄 필요 없음. 
            // 다음 글자 노드로 이동 (트리 타고 내려감) 
            now = now->child[phone_number[i] - '0'];
            // 문자열의 끝에 도달했다면 해당 글자 노드의 isEnd 를 True 로
            if (i == phone_number.length() - 1) now->isEnd = true;
        }
    }
    /* 트라이 트리에 phone_number 문자열을 타고 내려가되 중간에 isEnd 가 True 인 노드를 만나면 접두어가 있다고 판단함 */
    bool IsTherePrefix(string phone_number) {
        Trie* now = this; // 루트에서부터 시작 (루트 Trie 객체에서만 이 IsTherePrefix 를 한번 실행하도록 함. 재귀 안 쓰고 반복문 써서..)
        for (int i = 0; i < phone_number.length(); ++i) {
            if (now->child[phone_number[i] - '0'] != nullptr) {
                now = now->child[phone_number[i] - '0']; // 다음 글자 노드로 이동 (트리 타고 내려감) 
                if (now->isEnd) // 다음 글자가 있는 상태인데(위 if) isEnd 가 True 인 경우를 만났다는 것은 이 글자가 끝인 다른 단어가 있다는 것. 접두어! 
                    return true;
            }
            else // 다음 글자도 없다면(문자열 끝에 도달) 한번도 접두어가 없었던 것! (같은 문자열이 중복으로 주어지는 경우는 없다고 제한했으니 같은 문자열 접두사 있을 걱정은 안해도 되므로 그냥 더 이상 자식 없을 때까지 걸린적 없으면 접두사 없는 것임)
                return false;
        }
        return false;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t, n;
    cin >> t;
    
    for (int i = 0; i < t; ++i) {
        cin >> n;
        vector<string> phone_number_list(n);
        for (int j = 0; j < n; ++j)
            cin >> phone_number_list[j];
        sort(phone_number_list.begin(), phone_number_list.end()); // 정렬
        Trie* trie = new Trie(); // 트라이 트리의 루트 
        bool ok = true;
        for(auto phone_number : phone_number_list) {
            if (trie->IsTherePrefix(phone_number)) { // 접두사 있는지 검사
                ok = false;
                break;
            }
            trie->Insert(phone_number); // 접두사 없으면 추가
        }
        if (ok) cout << "YES" << '\n';
        else cout << "NO" << '\n';
    }
}

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

BOJ 카테고리 내 다른 글 보러가기