2018 KAKAO BLIND RECRUITMENT : [3차] 자동완성

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

코딩테스트 연습 - [3차] 자동완성

// 코드

import java.util.*;
 
class Solution {
    
    class Node {
        // 바로 다음 단언 즉 자신의 자식을 키로 가진다.
        HashMap<Character, Node> child = new HashMap<>();
        // 해당 노드가 말단 노드인지를 관리
        boolean isEnd = false;
        // 해당 노드가 몇번 중복이 되는지 횟수를 관리
        int branchSum = 0;
    }
    
    class Trie {
        // 루트노드는 어떠한 특정 값을 지니지 않는다.
        Node root;
        // 생성자를 통해 루트를 생성한다.
        public Trie() {root = new Node();}
        
        // 문자열을 분해해서 각 노드의 위치에 맞게 삽입해준다.
        public void insert(String word) {
            
            // 노드는 루트에서 시작한다.
            Node current = root;            
            // 노드를 하나씩 삽입해준다.
            for(Character c : word.toCharArray()) {
                // 해당 노드에 자식이 없는 경우
                if(current.child.get(c) == null) {
                    Node node = new Node();
                    current.child.put(c, node);
                    current = node;
                }
                // 해당 노드에 자식이 있는 경우
                else {
                    current = current.child.get(c);
                }
            }            
            // 반복문을 나왔을 경우 해당 노드의 마지막이므로 true처리를 해준다. 
            current.isEnd = true;
        }     
    }
    
    // 정의 : 각 노드의 중복횟수를 카운팅하여 반환한다.
    int makeBranchSum(Node now) {
        // 기저조건 : 자식이 없는 말단노드인 경우
        if(now.isEnd && now.child.isEmpty()) return now.branchSum = 1;
        
        // 자식 노드가 있을 경우 탐방을 한다.
        for(Node node : now.child.values()) now.branchSum += makeBranchSum(node);
        
        // 노드의 자체는 끝이지만 자식이 있는 경우 예를들어 go, gone에서 go가 해당된다.
        if(now.isEnd && !now.child.isEmpty()) now.branchSum += 1;
        
        return now.branchSum;
    }
    
    // 정의 : 단어별 최소 몇 번씩 타이핑 되어야 하는지를 카운팅하여 반환한다.
    int search(Node now, int cnt) {
        // 반환될 cnt값
        int ret = 0;
        // 기저조건 : 중복되는 횟수가 1인 경우
        if(now.branchSum == 1) return cnt;
        
        // 중복되는 단어가 있는 경우 계속 탐색한다.
        for(Node node : now.child.values()) ret += search(node, cnt+1);
        
        // 자식이 있지만 단어가 끝나는 경우. go, gone 에서 go(2) + gon(3) = 5
        if(now.isEnd) ret += cnt;
        
        return ret;
    }
    
    public int solution(String[] words) {
        
        // Trie객체 생성
        Trie trie = new Trie();
        
        // 각 단언들의 노드를 생성해준다.
        for(String word : words) trie.insert(word); 
        
        // 각 노드의 중복횟수를 카운팅한다.
        makeBranchSum(trie.root);
        
        // 최종 답을 구하여 반환한다.
        return search(trie.root, 0);
    }
}