[프로그래머스] Lv4 자동완성

링크: 2018 KAKAO BLIND RECRUITMENT > [3차] 자동완성

class Node {
    constructor(value = "") {
        this.value = value;
        this.children = new Map();
        this.hits = 1;
    }    
}

class Trie {
    constructor() {
        this.root = new Node();
    }
    insert(string) {
        let nodes = this.root.children;
        string.split("").forEach((ch, i) => {
            if (nodes.has(ch)) {
                nodes.get(ch).hits++;
                nodes = nodes.get(ch).children;                           
            }
            else {
                const newNode = new Node(string.slice(0, i + 1));
                nodes.set(ch, newNode);
                if (i === string.length-1) newNode.isLastChar = true;
                 nodes = newNode.children;  
            }
        });
    }
    
    find(string) {
        let cnt = 1;
        let nodes = this.root.children;
        for (const ch of string) {
            if (nodes && nodes.has(ch) && 
               (nodes.get(ch).value === string || nodes.get(ch).hits === 1)) {
                return cnt;
            }
            nodes = nodes.get(ch).children; 
            cnt++; 
        }    
        return cnt;
    }
}

function solution(words) {
    let answer = 0;
    const trie = new Trie();
    words.forEach(word => trie.insert(word));
    words.forEach(word => answer += trie.find(word));        
    return answer;
}

Trie 자료구조를 사용했다.
Node에 hits변수를 써서 해당 알파벳 노드를 몇번 방문했는지 카운트했다.
hits가 1이면 한번 방문한 것이고 그 아래에는 한 종류의 단어만 존재하므로 더이상 알파벳을 입력하지 않아도 된다.