[프로그래머스] [C++] 전화번호 목록 (trie)

1. 문제

 

전화번호 목록이 주어진다.

 

주어진 목록에서

 

다른 전화번호가  접두사인  전화번호가

 

있는지 없는지 찾아내는 프로그램을 작성하여라

 

2. TRIE

 

이 문제는 트라이로 문제를 해결할 수 있다.

 

트라이는 문자열의 각각 문자로 이루어진 트리이다.

 

문자열을 집어넣고 트리를 만들어나갈때

 

만약 새로운 트라이 노드를 만들지 않거나 (접두사로 포함되는 문자열을 삽입한 경우)

 

진행하던중 종료점이 있을경우 (접두사로 가지는 문자열을 삽입한 경우)

 

두 경우 만 찾으면 된다.

 

 

3. 코드

이것은 좋지 못한 코드이다.

소멸자에 delete 하는 과정이 없고

쓸모없는 number라는 코드가 있기 때문이다.

#include <string>
#include <vector>
#include <cstring>
 
using namespace std;
 
struct tri {
    bool number[10];
    bool isTerminal;
    tri* triNode[10];
    tri(): isTerminal(false)
    {
        memset(number, false, sizeof(number));
    }
    bool pushTri(const string& str)
    {
        int count = 0;
        tri* tmp = this;
        for(int i = 0; i < str.length(); i++)
        {
            int n = (int)str[i] - (int)'0';
            if(!tmp->number[n])
            {
                tmp->number[n] = true;
                tmp->triNode[n] = new tri();
                count++;
            }
            tmp = tmp->triNode[n];
            if(tmp->isTerminal)
                return true;
        }
        tmp->isTerminal = true;
        if(count == 0)
            return true;
        return false;
    }
};
 
bool solution(vector<string> phone_book) {
    tri dic;
    for(int i = 0; i < phone_book.size(); i++)
        if(dic.pushTri(phone_book[i]))
            return false;
    return true;
}

 

 

 

 

 

github.com/Nor-s/Algorithm/blob/master/programmers/PhoneBook.cpp

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