프로그래머스 - [3차]자동완성 (C++)

 Trie 자료구조를 공부하게 된 이유가 바로 이 문제 때문이었다. https://tigerfrom2.tistory.com/74

문자열 관리 자료구조 - 트라이(Trie) 개념/구현

대표 실습 문제라고도 할 수 있는데 Trie 자료구조에서 변수하나를 추가해줘야한다.

개념에서 알 수 있듯, 트라이 자료구조는 트리의 형태로 go -> gone 순으로 추가한다고 치면 g, o는 두번 방문될 것이고 n, e는 한번 방문될 것이다. 즉, 노드에 따로 방문 횟수를 저장한다.

그렇다면, 

go

gone

guild

라면, go를 탐색할 때 go 가 모두 탐색되면 지금까지 탐색한 갯수를 출력, 그리고 gone의 경우 gon 까지 탐색했을 때, n의 방 횟수는 1로 저장되어있을 것이다. 즉, 이 길로가면 끝은 1개밖에 없는 것이다. 그러므로 자동완성이 가능하다 판단한다.

 

그리고 c_str 이라는 함수를 알게 되었는데, string을 const char * 형태로 반환해주는 함수였다. 단, 원본 string이 바뀌면 안되는 주의사항이 있었다. 처음엔 그냥 string 을 사용해서 시간초과가 났는데 char 형태로 배열형식을 사용하니 통과되었다. 확실히, 벡터는 속도가 느리긴하다.... 하지만 너무 편리한데.. 

 

#include <string>
#include <vector>
#include <queue>
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int answer = 0;
struct Trie{
    bool finish;
    Trie *node[26];
    int num;
    Trie(){
        for(int i = 0; i < 26; i++)    node[i] = NULL;
        finish = false;
        num = 0;
    }
    
    void insert(const char *str){
        num += 1;
        if(*str == '\0') return;
        
        int index = *str - 'a';
        if(node[index] == NULL) node[index] = new Trie();
        
        node[index]->insert(str + 1);
    }
    
    
    int find(string str, int idx , int cnt){     
        int index = str[idx] - 'a';

        if(idx == str.size() - 1 || node[index]->num == 1){
             return cnt;
        }
        return node[index]->find(str, idx + 1, cnt + 1);
    }
};



int solution(vector<string> words) {
    int answer = 0;
    Trie* root = new Trie();
    for(int i = 0; i < words.size(); i++)    root->insert(words[i].c_str());
    for(int i = 0; i < words.size(); i++)    answer += root->find(words[i], 0, 1);
    
    return answer;
}