문제

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

---

입력

단어의 수 N과 단어들의 길이의 총합 L

---

출력

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

---

풀이

제한조건

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

접근방법

Trie 구조를 알고 있다면, 문제를 보자마자 해당 자료 구조를 이용해서 풀면 될 것이다.라는 생각이 들것이다.

문자열을 길이가 N이라 한다면, Insert와 Find가 모두 O(N)에 가능하다.

만약 공통문자열을 구하는 방식으로 한다면, N과 L의 크기로 인해 시간 또는 메모리 문제가 발생할 수 있을것으로 보인다.
(Programmers의 채점 기준 미공개로 인해 알 수 없음)

(Trie 구조 : https://velog.io/@hyeokkr/Trie)

주어지는 각 단어들을 Trie 구조에 모두 넣는다.
Trie 형태로 형성하며, 현재 문자에서 시작해서 하위 단어를 만들 수 있는 개수를 미리 카운팅 해둔다.

Trie 구조를 완성했다면, 순서대로 하나씩 꺼내며 확인한다.
하위 단어를 1개만 만들 수 있다면, 해당 단어가 입력되었을 때, 찾고자 하는 단어를 특정할 수 있으므로 자동완성이 가능하다.

만약 특정할 수 없다면, 단어를 전부 입력해 본다.

words = {"go","gone","guild"}

- go를 찾는 경우.
1. g를 입력했을 때, 3개 가능 따라서 특정할 수 없음.
2. go를 입력했을 때 단어가 일치하므로 종료

- gone를 찾는 경우.
1. g를 입력했을 때, 3개 가능 따라서 특정할 수 없음.
2. go를 입력했을 때, 2개 가능 따라서 특정할 수 없음.
3. gon을 입력했을 때, 1개 가능 따라서 특정할 수 있음.

- guild를 찾는 경우.
1. g를 입력했을 때, 3개 가능 따라서 특정할 수 없음.
2. gu를 입력했을 때, 1개 가능 따라서 특정할 수 있음.

---

코드

import java.util.*;

class TrieNode{
    public Map<Character, TrieNode> childNodes = new HashMap(); // 하위 문자 관리
    public int count; // 하위 단어들의 수
    public boolean isLast; // 마지막 문자인가?
}
class Trie{
    TrieNode root;
    
    Trie(){
        root = new TrieNode();
    }
    
    void insert(String word){
        TrieNode node = this.root;
        
        // 첫번째 문자부터 하위로 가면서, 파생단어의 수와 마지막 단어임을 기록
        for (int i = 0; i < word.length(); i++){
            node.count++;
            node = node.childNodes.computeIfAbsent(word.charAt(i), c -> new TrieNode());
        }
        node.count++;
        node.isLast = true;
    }
    
    int getMinTypingCount(String word){
        TrieNode node = this.root;
        
        int length = word.length();
        int last = length;
        
        for (int i = 0; i < length; i++){
            // 남은 하위 단어가 1개라면, 현재 입력으로 결정된다
            if(node.count == 1){
                last = i;
                break;
            }
            node = node.childNodes.get(word.charAt(i));
		}
        return last;
    }

}

class Solution {
    public int solution(String[] words) {
        Trie myTrie = new Trie();
        for(String str : words)
            myTrie.insert(str);
        
        int answer = 0;
        for(String str : words)
            answer += myTrie.getMinTypingCount(str);
        
        return answer;
    }
}