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

사용 언어 : javascript
해결 날짜 : 2023-05-17
해결 방법 :
- Trie를 활용해 문제 해결
  - words를 돌며 Trie에 insert
  - 다시 words를 돌며 Trie에 word find
    - 자동완성이 되는 경우는
      - Trie에 현재 단어의 첫 글자로 시작하는 단어가 현재 단어밖에 없거나,
      - 현재 단어를 Trie에서 찾는 과정에서 길이 두개 이상이거나(children이 여러개),
      - 현재 단어를 Trie에서 찾는 과정에서 중간 단어가 존재하는 경우(current.isEnd이면서 current.children.size !== 0인 경우)
    - str.length와 pos중 작은 값 반환
      - 자동완성이 되는 경우 : pos가 더 작음
      - 자동완성이 되지 않는 경우 : str.length가 더 작음
회고 :
- 단어 자동완성을 보고 바로 Trie 자료구조를 생각하고 문제를 해결했는데, 다른 사람의 풀이를 보니 words를 정렬 후 substring하는 방식도 있었다.
- Trie라고 단정짓지 않고 다른 접근 방식으로도 생각해야겠다.

코드

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

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

  insert(str) {
    let current = this.root;

    for (const c of str) {
      if (!current.children.has(c)) {
        current.children.set(c, new Node(current.value + c));
      }
      current = current.children.get(c);
    }
    current.isEnd = true;
  }

  find(str) {
    let current = this.root;
    let pos = 1;

    for (let i = 0; i < str.length; i++) {
      current = current.children.get(str[i]);

      if (current.children.size >= 2 || (current.isEnd && current.children.size !== 0)) {
        pos = current.value.length + 1;
      }
    }

    return Math.min(str.length, pos);
  }
}

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;
}

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges