프로그래머스] C++ 해시 - 전화번호 목록(Level 2)

 

 

phone_book에 있는 문자열들 중 접두사가 중복되는 경우가 있으면 false, 없으면 true를 반환하는 문제입니다.

 

예를들어 예제에 나와있는것 처럼

 

"119", "97674223", "1195524421" 이 있다고 가정한다면

 

"119"는 "1195524421"에 중복되므로 false입니다.

 

반면

 

"123", "456", "789" 부분은 중복되는것이 없으므로 true입니다.

 

 

 

문자를 하나씩 비교하는 방법도 있지만 비효율적이라는 판단이 서서 트라이(trie)구조로 풀었습니다.

 

트라이구조는 https://hwan-shell.tistory.com/133?category=771708 에서 확인하시면 됩니다.

 

#include <string>
#include <vector>
#include <iostream>

#define NUMBER 10

using namespace std;
bool answer;
class trie{
private:
    trie * c_node[NUMBER];
    bool check;
public:
    
    trie(){
        check = false;
        for(int i = 0; i < NUMBER; i++)
            c_node[i] = NULL;
    }
    ~trie(){
        for(int i = 0; i < NUMBER; i++)
            if(c_node[i] != NULL)
                delete c_node[i];
    }
    
    int tonum(char c){ return c - '0'; }
    
    void insert(const char * word){
    
        if(*word == '\0'){
            check = true;    //문자의 끝에 도달하면 마지막인 것 체크
            for(int i = 0; i < NUMBER; i++)    
                if(c_node[i] != NULL)    //중복되는 경우 1
                    answer = false;
                
            return;
        }           
        
        if(check == true){        //중복되는 경우 2
            answer = false;
            return;
        }
        
        int next = tonum(*word);
        
        if(c_node[next] == NULL){
            c_node[next] = new trie();
        }
        c_node[next]->insert(word + 1);
    }
    
};

bool solution(vector<string> phone_book) {
    
    trie t_trie;
    
    for(int i = 0; i < phone_book.size(); i++){
        answer = true;
        t_trie.insert(phone_book[i].c_str());
        if(answer == false)
            return false;
    }    
    return answer;
}
​

 

 

 

중복되는 경우 1

 

"19955421" 문자열이 먼저 들어가고 그 후 "199"가 들어 갔을 때.

.

나중에 입력된 문자는 "199"에서 끝났지만 다음 노드를 살펴보니 NULL이 아닌 값이 있으므로 false.

만약 모두다 NULL이면 "199"는 중복되는 숫자가 없는것으로 판단.

 

 

 

중복되는 경우 2

 

"199"가 먼저 들어가고 "19955421"문자열이 나중에 들어갔을 때.

 

"19955421"문자열이 나중에 들어갔다고 한다면 "199"까지 들어간 후 "55421"을 더 넣을지 판단해야 합니다.

하지만 앞서 "199"문자열이 먼저 들어갔으므로 check변수는 true입니다. 따라서 check를 확인했을 때 먼저 들어온

문자열이 있다면 중복된 것이므로 false를 반환합니다.