본문 바로가기
# 사용하지 않는 게시글/알고리즘 문제

[프로그래머스 - 해시] 전화번호 목록

by cy_mos 2019. 4. 8.
반응형

[프로그래머스 - 해시] 전화번호 목록


📄 [해시] 전화번호 목록 C++ Source Code

#include <string>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

#define MAX_LEN 20
#define TO_NUMBER(X) X - '0'

typedef struct TrieNode {
    
    bool terminate = false;
    TrieNode * child[MAX_LEN];
    
    TrieNode() { memset(child, 0, sizeof(child)); }
    ~TrieNode() {
        for (int ii = 0; ii < MAX_LEN; ii++) { if (child[ii]) { delete child[ii]; } }
    }
    
    void insert(const char * key) {
        if (*key == 0) { terminate = true; }
        else {
            const int next = TO_NUMBER(*key);
            if (child[next] == NULL) { child[next] = new TrieNode(); }
            child[next]->insert(key + 1);   
        }
    }
    
    TrieNode* find(const char * key) {
        if (*key == 0) { return this; }
        
        const int next = TO_NUMBER(*key);
        if (child[next] == NULL) { return NULL; }
        return child[next]->find(key + 1);
    }
    
} Trie;

bool solution(vector<string> phone_book) {
    
    bool answer = true;
    sort(phone_book.begin(), phone_book.end(), greater<string>());
    
    TrieNode * head = new TrieNode();
    for (const auto prefix : phone_book) {
        if (head->find(prefix.c_str()) != NULL) { answer = false; break; }
        head->insert(prefix.c_str());
    }
    
    delete head;
    return answer;
}

🚀 REFERENCE

반응형

댓글