[Algospot] SOLONG 안녕히, 물고기는 고마웠어요! (Python, Trie)

[문제 링크](https://www.algospot.com/judge/problem/read/SOLONG)

이 문제는 타이핑 시 **빈도가 잦은 문자를 추천**하는 기능을 구현하는 문제입니다.

<br>
<br>

### 제약조건

**입력**

사전에 포함된 단어의 수 N (1 <= N <= 10000)
입력할 단어의 수 M (1 <= M <= 20000)이 주어집니다. 

그 후 N 줄에는 한 줄에 하나의 문자열과 정수로 사전에 포함된 단어와 해당 단어의 출현 빈도가 **사전 순서와 무관**하게 주어집니다. 

**같은 단어가 두번 이상 주어지는 일은 없으며**, 출현 빈도는 1 과 10만 사이의 정수입니다. 

그 다음 줄에 M개의 단어로 입력할 문자열이 주어집니다. 

**모든 단어는 알파벳 대문자이며, 길이는 최대 10입니다.**

<br>
<br>

### 핵심내용

단어의 접두사부터 시작해 접미사를 찾아내는데는 `Trie` 가 적합할 수 있습니다.
`Trie` 자료구조 고려 시 신경쓸 점은 사이즈가 되겠습니다.

이번 문제에서 주어진 정보로 모든 단어는 최대 길이는 **10**, 사전에 포함된 단어의 수는 최대 **10000** 

이를 종합하면 기본적으로 생성되는 `Trie` 의 노드 수는 **100000** 이 됩니다.
그리고 각 노드당 대문자 수만큼(**26**)의 children 을 가집니다.

하지만 이번 문제는 문자의 존재 여부가 아닌 잦은 빈도의 문자를 추천 받는 것으로
각 노드 당 잦은 빈도의 문자를 가지고 있어야합니다. (다뤄지는 문자들을 실제 동작 전에 알 수 있음으로 이를 배열에 관리해 노드에는 실제 문자가 아닌 배열 속 문자의 인데그를 저장시킵니다. (4바이트)

이러한 부분은 노드들이 `first`, `terminal` 값을 가짐으로 구현됩니다.

`first` 는 해당 노드에 가장 먼저 추천 문자로 들어온 문자의 인덱스입니다.
`terminal` 은 이 노드가 특정 문자의 종료 노드인지를 의미하며 동시에 특정 문자의 인덱스를 가집니다. 사실 기존 방식에서 `terminal`은 boolean 으로 구현하여 특정 문자가 `Trie` 에 존재하는지를 따졌지만 이번엔 문자끼리의 비교가 필요해 문자의 인덱스를 저장하게 되었습니다.

잊으면 안될 이번 문제의 핵심은 빈도가 높은 순으로 추천해야하는 것입니다.
만약 빈도가 같다면 사전순으로 빠른 쪽을 추천해야합니다.

사실 이 부분을 find 시 동적으로 다 찾으려하면 코드의 복잡도가 상당히 올라갑니다.
다행스럽게도 위에서 한 번 언급한 것 같이 **다뤄지는 문자들을 실제 동작 전에 알 수 있고** 이는 Greedy 관점에서 볼 때 빈도를 대상으로 내림차순, 문자를 대상으로 오름차순으로 정렬하여 차례대로 `Trie` 를 생성하면 동적으로 추천 문자를 찾아낼 필요 없이 자연스럽게 추천 문자를 찾을 수 있습니다. 

<br>
<br>

### 구현 코드 (Python)

```
from sys import stdin

ROOT = 0
nextId = 1
MX = 10000 * 10 + 5
terminal = [-1] * MX
children = [[-1] * 26 for _ in range(MX)]
first = [-1] * MX
strings = []

def to_index(ch):
    return ord(ch) - ord('A')

def insert_string(string_id):
    global ROOT, nextId, terminal, children, first, strings
    cur_node = ROOT
    for char in strings[string_id]:        
        char_idx = to_index(char)
        if children[cur_node][char_idx] == -1:
            children[cur_node][char_idx] = nextId
            first[nextId] = string_id
            nextId += 1
        cur_node = children[cur_node][char_idx]
    terminal[cur_node] = string_id

def find_min_keystrokes(s):
    global ROOT, terminal, children, first, strings
    cur_node = ROOT
    strokes = 0
    for char in s:
        char_idx = to_index(char)
        child_id = children[cur_node][char_idx]
        if child_id == -1:
            return len(s)
        strokes += 1
        if terminal[child_id] != -1 and strings[terminal[child_id]] == s:
            return len(s)
        if strings[first[child_id]] == s:
            return strokes + 1
        cur_node = child_id
    return len(s)

for _ in range(int(stdin.readline())):
    ROOT = 0
    nextId = 1
    MX = 10000 * 10 + 5
    terminal = [-1] * MX
    children = [[-1] * 26 for _ in range(MX)]
    first = [-1] * MX
    strings = []

    n, m = map(int, stdin.readline().split())

    for _ in range(n):
        s, freq = stdin.readline().split()
        freq = int(freq)
        strings.append((freq, s))
    
    strings.sort(key=lambda x: (-x[0], x[1]))

    strings = [s for _, s in strings]

    for string_id in range(len(strings)):
        insert_string(string_id)
    
    original_string = stdin.readline().strip()
    whitespace_count = len(original_string.split()) - 1
    total_keystrokes = whitespace_count

    for word in original_string.split():
        total_keystrokes += find_min_keystrokes(word)
    
    print(total_keystrokes)
```