[2018 KAKAO BLIND RECRUITMENT[3차]] 자동완성

뭔가 이름으로 보건데 너무 무섭게 생겨서 미뤄뒀던 trie 를 공부해서 풀었다. 

trie만 알고나니 풀기 너무 쉬웠던 문제이다. 자칫하면 영영 못 찾을뻔한 반례가 있었는데 

짐작컨데, 테스트 케이스 중에 띄어쓰기가 있는 것 같다. 왜냐하면 \0 이 나오면 -1 을 리턴하도록 짰는데

이것을 없에니깐 accept 되었기 때문이다. 

이러한 문제유형은 어떠한 특정한 자료구조를 알기만 하면 매우 쉽게 풀 수 있는 것 같다. 

#include <string>
#include <iostream>
#include <cstring>
#include <vector>
#define ALPHA 26
// 10:04 =>
using namespace std;

class Trie {
    int acc;
    Trie* children[ALPHA];
    bool terminal;
    
public:
    
    Trie() : acc(0) {
        terminal = false;
        memset(children, 0, sizeof(children));
    }
    
    ~Trie() {
        for (int i=0; i < ALPHA; i++) 
            if (children[i]) delete children[i];
    }
    
    int char_to_index(char c) {
        return c - 'a';
    }
    
    void insert(const char* key) {
        if (*key == '\0') {
            terminal = true;
        } else {
            int index = char_to_index(*key);
            if (!children[index]) children[index] = new Trie();
            terminal = false;
            children[index]->insert(key+1);
        }
        acc++;
    }
    
    int find(const char* key, int cnt) {
        if (*key == '\0') return cnt;
        if (acc == 1) return cnt;
        int index = char_to_index(*key);
        return children[index]->find(key+1, cnt+1);
    }
};

int solution(vector<string> words) {
    int answer = 0;
    Trie* trie = new Trie();
    for (string word: words) {
        trie->insert(word.c_str()); 
    }
    for (string word: words) {
        int find_rst =  trie->find(word.c_str(), 0);
        answer += find_rst;
    }
    return answer;
}