[프로그래머스] ⌨[3차] 자동완성

😀문제 설명

자동완성

포털 다음에서 검색어 자동완성 기능을 넣고 싶은 라이언은 한 번 입력된 문자열을 학습해서 다음 입력 때 활용하고 싶어 졌다. 예를 들어, go 가 한 번 입력되었다면, 다음 사용자는 g 만 입력해도 go를 추천해주므로 o를 입력할 필요가 없어진다! 단, 학습에 사용된 단어들 중 앞부분이 같은 경우에는 어쩔 수 없이 다른 문자가 나올 때까지 입력을 해야 한다.
효과가 얼마나 좋을지 알고 싶은 라이언은 학습된 단어들을 찾을 때 몇 글자를 입력해야 하는지 궁금해졌다.

예를 들어, 학습된 단어들이 아래와 같을 때

go
gone
guild

• go를 찾을 때 go를 모두 입력해야 한다.
• gone을 찾을 때 gon 까지 입력해야 한다. (gon이 입력되기 전까지는 go 인지 gone인지 확신할 수 없다.)
• guild를 찾을 때는 gu 까지만 입력하면 guild가 완성된다.

이 경우 총 입력해야 할 문자의 수는 7이다.

라이언을 도와 위와 같이 문자열이 입력으로 주어지면 학습을 시킨 후, 학습된 단어들을 순서대로 찾을 때 몇 개의 문자를 입력하면 되는지 계산하는 프로그램을 만들어보자.

---

😁입력 형식

학습과 검색에 사용될 중복 없는 단어 N개가 주어진다.
모든 단어는 알파벳 소문자로 구성되며 단어의 수 N과 단어들의 길이의 총합 L의 범위는 다음과 같다.

• 2 <= N <= 100,000
• 2 <= L <= 1,000,000

---

😂출력 형식

단어를 찾을 때 입력해야 할 총 문자수를 리턴한다.

---

🤣입출력 예제

words	result
["go","gone","guild"]	7
["abc","def","ghi","jklm"]	4
["word","war","warrior","world"]	15

---

😄입출력 설명

• 첫 번째 예제는 본문 설명과 같다.
• 두 번째 예제에서는 모든 단어들이 공통된 부분이 없으므로, 가장 앞글자만 입력하면 된다.
• 세 번째 예제는 총 15 자를 입력해야 하고 설명은 아래와 같다.
  • word는 word모두 입력해야 한다.
  • war는 war 까지 모두 입력해야 한다.
  • warrior는 warr 까지만 입력하면 된다.
  • world는 worl까지 입력해야 한다. (word와 구분되어야 함을 명심하자)

해설 보러가기

---

😅나의 풀이

해설도 보고 질문하기 탭의 도움을 참 많이 받았다.
효율성 문제를 해결하기 위해 정렬 또는 Trie 알고리즘을 사용해야하는데, 이왕 풀이를 한다면 써보지 못한 알고리즘을 사용하고 싶었음

간단히 요약하자면, 부모 - 자식 관계로 문자열을 순회하며 생성된 Trie 구조에 한번만 호출된 문자가 나올 때까지 카운트를 증가시켜 답을 구한다.

즉 첫번째 테스트 케이스는 go, gon, gu 가 나오게 되며,

• g는 3번
• o는 2번
• n은 1번
• u는 1번

답이 7회가 된다.

class Node {
  constructor(value = "", numOfWords = 0) {
    this.value = value;
    this.numOfWords = numOfWords;
    this.child = new Map();
  }
}

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

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

    for (const char of string) {
      if (!cur_node.child.has(char)) {
        cur_node.child.set(char, new Node(cur_node.value + char));
      }
      cur_node = cur_node.child.get(char);
      cur_node.numOfWords += 1; // 현재 노드를 포함하는 단어 수를 업데이트
    }
  }

  min_len(string) {
    let cur_node = this.root;
    let len = 0;

    for (const char of string) {
      cur_node = cur_node.child.get(char);
      len++;
      if (cur_node.numOfWords === 1) return len; // 현재 노드를 포함하는 단어가 하나라면 해당 길이 반환
    }
    return len;
  }
}

function solution(words) {
  const trie = new Trie();

  words.forEach((item) => trie.insert(item)); // 주어진 단어들로 Trie 구축

  // 문자가 호출된 수의 합
  return words.map((item) => trie.min_len(item)).reduce((a, b) => a + b);
}