문제

link: https://programmers.co.kr/learn/courses/30/lessons/17685

주어진 단어들에서 각각 자동완성을 하기 위해 입력해야 하는 최소 글자 수를 구한다.

접근 및 풀이

단어들을 알파벳 단위의 시퀀스로 생각하고 이를 이용해서 트리형태(앞 글자가 뒷 글자의 부모)로 만들고, 모든 leaf node에서 부모를 탐색하며 처음으로 자식 노드가 2개 이상인 경우의 depth를 찾이면 될 것 이라고 접근하였다.

(이렇게 문자열들의 접두사를 기준으로 트리를 만드는 것을 trie라고 한다. 참고: https://www.crocus.co.kr/1053)

구현 및 코드

클래스를 따로 사용하지 않고 array나 문자열 그대로 구현하면 더 깔끔하고 짧게 코드 구현이 될 것 같은데, 생각이 잘 안 되어서 직접 node를 구현해서 trie 구조를 만들어 구현하였다.

class Node {
  constructor(key, parent, children, depth) {
    this.parent = parent;
    this.children = children;
    this.depth = depth;
    this.num = 0;
    this.key = key;
  }
  addChild(key, child) {
    this.children[key] = child;
    this.num += 1;
  }
  isPrefix() {
    return this.num > 1 || this.depth === 0;
  }
  getParent() {
    return this.parent;
  }
  getChildren() {
    return this.children;
  }
  getNextDepth() {
    return this.depth + 1;
  }
}
const ROOT = new Node("ROOT", null, {}, 0);
const LEAVES = [];

function setTrie(word) {
  let curr = ROOT;
  let children = curr.getChildren();
  let key;
  let newNode;
  for (let i = 0; i < word.length; i += 1) {
    key = word[i];
    if (!children[key]) {
      newNode = new Node(key, curr, {}, curr.getNextDepth());
      curr.addChild(key, newNode);
    }
    newNode = children[key];
    curr = children[key];
    children = children[key].getChildren();
  }
  curr.addChild("LEAF", curr, {}, curr.getNextDepth());
  LEAVES.push(newNode);
}

function getResult() {
  let ret = 0;
  LEAVES.forEach((node) => {
    let curr = node;
    if (curr.isPrefix()) {
      ret += curr.depth;
    } else {
      while (!curr.isPrefix()) {
        curr = curr.getParent();
      }
      ret += curr.getNextDepth();
    }
  });
  return ret;
}

function solution(words) {
  words.forEach((word) => {
    setTrie(word);
  });
  return getResult();
}