[Java] 2018 카카오 블라인드 (자동 완성)

문제 설명

---

자동완성

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

출력 형식

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

입출력 예제

wordsresult

["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를 사용해 해결할 수 있다는 것을 바로 떠올릴 수 있었을 것입니다.

 

 저는 문제를 풀기 위해 Trie의 한 노드가 가지는 자료를 3가지를 정의하였습니다.

1. child HashMap<Character, Node> child = new HashMap();

2. boolean isEnd;

3. int branchSum;

 

1번 child는 노드의 child노드를 연결하기 위한 링크 역할을 합니다.

2번 isEnd는 단어의 끝인지의 여부를 나타냅니다.

3번 branchSum은 뻗어있는 가지의 수를 의미합니다. (isEnd == true)인 구간, 즉 단어의 끝을 가지는 부분도 하나의 가지로 계산합니다.

 

만약 단어가 go, gone, guild가 주어진다면 branchSum의 상태는 아래의 그림과 같습니다.

아래와 같은 코드로 branchSum을 계산할 수 있습니다.

public int makeBranchSum(Node now){

	if(now.isEnd && now.child.isEmpty()) //단어의 끝이면서 더 나아갈 깊이가 없는 경우
		return now.branchSum = 1;

	for(Node node : now.child.values())
		now.branchSum += makeBranchSum(node);

	//단어의 끝이지만 더 나아갈 깊이가 있는 경우, 위 그림에서 노드(o)에 해당
	if(now.isEnd && !now.child.isEmpty()) 
		now.branchSum += 1;
	return now.branchSum;
} 

 

 

 isEnd와 branchSum을 적절히 활용하면 문제를 해결할 수 있습니다.

1. 일단 처음으로 (branchSum == 1)인 구간에 도달한다면 더 이상의 가지가 뻗어있지 않다는 의미가 되므로 그 구간까지의 깊이를 반환하고, 더 깊은 곳으로 진입하지 않습니다.

2. 만약 branchSum != 1이고 isEnd == true인 경우면 더 나아갈 수 있는 가지는 남아있으나, 여기가 어떠한 단어의 끝이라는 의미가 되므로 그 구간까지의 깊이를 포함하여 더해줍니다.

public int search(Node now, int cnt){ //cnt는 깊이를 의미
        
	int ret = 0;

	if(now.branchSum == 1) //1번 항목 검사
		return cnt;

	for(Node node : now.child.values())
		ret += search(node, cnt + 1);
	if(now.isEnd) //2번 항목 검사
		ret += cnt;

	return ret;
}

 

 

소스 코드

---

import java.util.*;

class Solution {
    
    public class Node {
        HashMap<Character, Node> child = new HashMap();
        boolean isEnd = false;
        int branchSum = 0;
    }
    
    public 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);
            }
            current.isEnd = true;
        }
    }
    
    public int makeBranchSum(Node now){
        
        if(now.isEnd && now.child.isEmpty())
            return now.branchSum = 1;
        
        for(Node node : now.child.values())
            now.branchSum += makeBranchSum(node);
        
        if(now.isEnd && !now.child.isEmpty())
            now.branchSum += 1;
        return now.branchSum;
    } 
    
    public int search(Node now, int cnt){
        
        int ret = 0;
        
        if(now.branchSum == 1)
            return cnt;
        
        for(Node node : now.child.values())
            ret += search(node, cnt + 1);
        if(now.isEnd)
            ret += cnt;
        
        return ret;
    }
    
    public int solve(String[] words){
        
        Trie trie = new Trie();
        
        for(int i=0;i<words.length;i++){
            String word = words[i];
            trie.insert(word);
        }
        makeBranchSum(trie.root);
        return search(trie.root, 0);
    }
    
    public int solution(String[] words) {
        int answer = 0;
        return answer = solve(words);
    }
}