자동완성 (프로그래머스)

class Node {
  constructor(value = '') {
    this.value = value;
    this.children = new Map();
    this.count = 0;
  }
}

class Trie {
  constructor() {
    this.root = new Node();
  }

  insert(string) {
    let currentNode = this.root;

    for (const char of string) {
      if (!currentNode.children.has(char)) {
        currentNode.children.set(char, new Node(currentNode.value + char));
      }

      currentNode = currentNode.children.get(char);
      currentNode.count += 1;
    }
  }

  has(string) {
    let currentNode = this.root;

    for (const char of string) {
      if (!currentNode.children.has(char)) {
        return false;
      }

      currentNode = currentNode.children.get(char);
    }

    return true;
  }

  getCount(string) {
    let currentNode = this.root;
    let totalCount = 0;

    for (const char of string) {
      totalCount += 1;
      currentNode = currentNode.children.get(char);
      if (currentNode.count === 1) {
        return totalCount;
      }

    }

    return totalCount;
  }
}

function solution(words) {
    let answer = 0;
    let mT = new Trie();
    for (let word of words) {
        mT.insert(word);
    }
    for (let word of words) {
        answer += mT.getCount(word);
    }
    return answer;
}

=> 사전에 쓰는 트라이 자료구조를 이용하는 문제이다. 솔직히 처음 봤을 때... 감도 안 왔다. 노드는 마지막 요소인지와 카운트 그리고 자식 요소를 저장한다. 그 다음 트라이 구조체는 트리와 유사하지만, 단어를 저장하는 점에서 차이를 보인다. 요소를 추가하는 것과 단어의 최소 길이를 구하는 getCount를 구해야한다. 각 최소 단어 수를 추출한 후 answer를 구한다.