문제

포털 다음에서 검색어 자동완성 기능을 넣고 싶은 라이언은 한 번 입력된 문자열을 학습해서 다음 입력 때 활용하고 싶어 졌다. 예를 들어, 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와 구분되어야 함을 명심하자)

---

풀이

먼저 입력받은 words로 Trie 구조를 만들어서 하위에 어떤 문자들이 미리 알아야 셀 수 있다.
예를 들어, guild를 찾을 때, gu만 입력해도 된다는 것을 알려면 Trie 구조에 해당 정보들을 넣어놔야 한다.

Trie 구조 만드는 법

1. go를 넣는다.

• root의 자식 노드로 g를 추가한다.
  이때 g 노드에 단어가 추가되었음을 표시하기 위해 카운팅을 해줘야 한다.
  따라서 ('g', 1)과 같은 형태로 저장해줘야 한다.
• g의 자식 노드로 o를 추가한다. ➡️ ('o', 1)

2. gone을 넣는다.

• root의 자식 노드로 g를 추가한다.
  이때 g 노드에 단어가 추가되었음을 표시하기 위해 카운팅을 해준다.
  따라서 카운팅이 추가되어 ('g', 2)과 같은 형태로 저장된다.
• g의 자식 노드로 o를 추가한다. ➡️ ('o', 2)
• o의 자식 노드로 n을 추가한다. ➡️ ('n', 1)
• n의 자식 노드로 e를 추가한다. ➡️ ('e', 1)

3. guild를 넣는다.

• root의 자식 노드로 g를 추가한다. ➡️ ('g', 3)
• g의 자식 노드로 u를 추가한다. ➡️ ('u', 1)
• u의 자식 노드로 i를 추가한다. ➡️ ('i', 1)
• i의 자식 노드로 l를 추가한다. ➡️ ('l', 1)
• l의 자식 노드로 d를 추가한다. ➡️ ('d', 1)

이렇게 하면 완성된 트라이 구조는 아래가 된다.

     [3, 'g']
      /    \
[1, 'u'] [2, 'o']
   |         |
[1, 'i'] [1, 'n']
   |         |
[1, 'l'] [1, 'e']
   |        
[1, 'd'] 

Trie 구조가 완성되었다면, 이후 각 단어들을 찾으면서 카운팅이 1이라면 이후 글자를 입력하지 않아도 된다는 것을 알 수 있으므로 그 지점에서 카운팅을 멈추면 된다.

---

코드

function makeTrie(words) {      // 단어 배열을 받아서 trie를 만들어주는 함수
    const root = {};            // words = ['go', 'gone', 'guild']
    for (const word of words) { // word = 'go'
        let current = root;     // 현재 노드 = 루트부터 시작한다.
        for (const char of word) { // char = 'g'
            if (!current[char]) current[char] = [0, {}]; // 현재 노드의 자식에 'g'가 없다면, g: [0, {}] 노드를 추가한다.
            current[char][0] = (current[char][0] || 0) + 1; // root의 자식 노드인 'g' 카운팅에 1을 더해준다.
            current = current[char][1]; // 자식 노드('g')로 이동
        }
    }
    return root; // 트라이 반환
}

function solution(words) {
    let answer = 0;
    const trie = makeTrie(words); // 트라이 담겨있음
    
    for (const word of words) { // word = 'go'
        let count = 0; // 'go'를 찾으려면 몇 개의 문자를 입력해야하는지 세는 변수
        let current = trie; // 루트부터 시작
        for (const [index, char] of [...word].entries()) { // index = 0, char = 'g'
            count += 1; // 반복문을 돌 때마다 count + 1
            if (current[char][0] <= 1) { // 단어가 하나 이하로 남을 경우 종료한다.
                break;
            }
            current = current[char][1]; // 다음 노드로 이동한다.
        }
        answer += count; // 문자를 입력한 카운트를 더해준다.
    }
    return answer;
}

Array.entries()

entries() 메소드는 배열의 각 인덱스에 대한 키/값 쌍을 가지는 Array Iterator 객체를 반환한다.

const array = ['a', 'b', 'c'];

const iterator = array.entries();

console.log(iterator.next().value); // Array[0, 'a']
console.log(iterator.next().value); // Array[1, 'b']