프로그래머스 - 전화 번호 목록

https://programmers.co.kr/learn/courses/30/lessons/42577

접근

전화번호가 최대 100만개가 들어올 수 있으므로 절대로 일일이 비교하면 안됩니다.

카테고리가 해쉬여서 해쉬를 이용해야 되나 했는데, 결론적으론 Trie구조를 이용했습니다.

이유는

1. 올수있는 문자열이 숫자만 가능합니다. 즉 노드당 최대 자식노드의 개수는 10개입니다.
2. 번호의 길이는 최대 20자 입니다. 즉 탐색 시 최대 깊이는 20 입니다.

구현

전화번호를 모두 Trie구조에 넣은 후 탐색하는 방식입니다.

다음과 같은 2가지 상황이 발생하면 해당 번호가 다른 번호의 접두어라고 판단 할 수 있습니다.

1. 탐색 대상 문자열이 끝나지 않았음에도 terminal node에 도착한 경우
   ex) '119'가 Trie에 들어있을 때, '119234'을 검색했을 때

2. 탐색 대상 문자열이 끝났는데도 terminal node가 아닌 경우
   ex) '119234'가 Trie에 들어있을 때, '119'를 검색했을 때

반면 위 두 경우가 아닌, 즉 탐색 대상 문자열이 끝났고 terminal node일때는 검색하는 대상 자기 자신의 노드에 도달했다고 판단하였습니다.

후기

어렵지 않게 풀었습니다. 다만 다양한 접근이 가능하므로 여러 풀이법을 생각해 보아야겠습니다.

다음은 코드전문입니다.

#include <string>
#include <vector>
#include <string.h>

using namespace std;

struct Trie{
    Trie* child[10];
    bool isNum;
    
    Trie(): isNum(false) {
        memset(child,0,sizeof(child));
    }
    
    ~Trie(){
        for(int i = 0 ; i < 10 ; i++){
            if(child[i]){
                delete child[i];
            }
            
        }
    }
    
    void insert(const char* key){
        if (*(key) == '\0') {
            isNum = true;
            return;
        }else{
            int curr = *(key) - '0';
            if (child[curr] == NULL) {
                child[curr] = new Trie();
            }
            child[curr]->insert(key+1);
        }
    }
    
    bool find(const char* key){
        if (*(key) != '\0' && isNum) {
            return false;
        }else if(*(key) == '\0' && !isNum) return false;
        else if(*(key) == '\0' && isNum){
            return true;
        }else{
            int curr = *(key)-'0';
            return child[curr]->find(key+1);
        }
        
    }
    
};


bool solution(vector<string> phone_book) {
    bool answer = true;
    Trie* root = new Trie();
    
    for(int i = 0 ; i < phone_book.size() ; i++){
        root->insert(phone_book[i].c_str());
    }
    
    for(int i = 0 ; i < phone_book.size() ; i++){
        if(!(root->find(phone_book[i].c_str()))){
            answer = false;
            break;
        }
    }
    
    
    return answer;
}