[BOJ] 백준 5670번 휴대폰 자판 (Java)

#5670 휴대폰 자판

난이도 : 플레 4

유형 : 문자열 / 트라이

5670번: 휴대폰 자판

▸ 문제

휴대폰에서 길이가 P인 영단어를 입력하려면 버튼을 P번 눌러야 한다. 그러나 시스템프로그래밍 연구실에 근무하는 승혁연구원은 사전을 사용해 이 입력을 더 빨리 할 수 있는 자판 모듈을 개발하였다. 이 모듈은 사전 내에서 가능한 다음 글자가 하나뿐이라면 그 글자를 버튼 입력 없이 자동으로 입력해 준다! 자세한 작동 과정을 설명하자면 다음과 같다.

1. 모듈이 단어의 첫 번째 글자를 추론하지는 않는다. 즉, 사전의 모든 단어가 같은 알파벳으로 시작하더라도 반드시 첫 글자는 사용자가 버튼을 눌러 입력해야 한다.
2. 길이가 1 이상인 문자열 c1c2...cn이 지금까지 입력되었을 때, 사전 안의 모든 c1c2...cn으로 시작하는 단어가 c1c2...cnc로도 시작하는 글자 c가 존재한다면 모듈은 사용자의 버튼 입력 없이도 자동으로 c를 입력해 준다. 그렇지 않다면 사용자의 입력을 기다린다.

예를 들면, 사전에 "hello", "hell", "heaven", "goodbye" 4개의 단어가 있고 사용자가 "h"를 입력하면 모듈은 자동으로 "e"를 입력해 준다. 사전상의 "h"로 시작하는 단어들은 모두 그 뒤에 "e"가 오기 때문이다. 그러나 단어들 중 "hel"로 시작하는 것도, "hea"로 시작하는 것도 있기 때문에 여기서 모듈은 사용자의 입력을 기다린다. 이어서 사용자가 "l"을 입력하면 모듈은 "l"을 자동으로 입력해 준다. 그러나 여기서 끝나는 단어인 "hell"과 그렇지 않은 단어인 "hello"가 공존하므로 모듈은 다시 입력을 기다린다. 사용자가 "hell"을 입력하기 원한다면 여기서 입력을 멈출 것이고, "hello"를 입력하기 원한다면 직접 "o" 버튼을 눌러서 입력해 줘야 한다. 따라서 "hello"를 입력하려면 사용자는 총 3번 버튼을 눌러야 하고, "hell", "heaven"은 2번이다. "heaven"의 경우 "he"에서 "a"를 입력하면 바로 뒷부분이 모두 자동으로 입력되기 때문이다. 비슷하게, "goodbye"는 단 한 번만 버튼을 눌러도 입력이 완료될 것이다. "g"를 입력하는 순간 뒤에 오는 글자가 항상 유일하므로 끝까지 자동으로 입력되기 때문이다. 이때 사전에 있는 단어들을 입력하기 위해 버튼을 눌러야 하는 횟수의 평균은 (3 + 2 + 2 + 1)/4 = 2.00이다.

사전이 주어졌을 때, 이 모듈을 사용하면서 이와 같이 각 단어를 입력하기 위해 버튼을 눌러야 하는 횟수의 평균을 구하는 프로그램을 작성하시오.

▸ 입력

입력은 여러 개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스의 첫째 줄에 사전에 속한 단어의 개수 N이 주어지며(1 ≤ N ≤ 105), 이어서 N개의 줄에 1~80글자인 영어 소문자로만 이루어진 단어가 하나씩 주어진다. 이 단어들로 사전이 구성되어 있으며, 똑같은 단어는 두 번 주어지지 않는다. 각 테스트 케이스마다 입력으로 주어지는 단어의 길이 총합은 최대 106이다.

▸ 출력

각 테스트 케이스마다 한 줄에 걸쳐 문제의 정답을 소수점 둘째 자리까지 반올림하여 출력한다.

 

문제 풀이  

트라이의 개념을 알고있다면 쉽게 접근이 가능하고 모른다면... 공부를 하고 다시 접해야 할 문제인 것 같다. 트라이는 메모리 사용량이 엄청 크다는 단점이 있지만 문자열 탐색에 있어서 일반 자료구조를 사용하는 것보다 빠르게 탐색할 수 있다는 장점을 가지고 있다. 그래서 문자열 탐색은 트라이(Trie)로 풀이하는 것이 좋다.

 

설계 및 구현

입력으로 주어지는 문자열들을 트라이 자료구조에 저장을 해준다. 그 다음 각 입력 데이터들을 하나하나 넣어가며 모듈을 사용하였을 때 입력해야하는 키보드의 수를 카운트하여 계산해주면 된다.  트라이를 안다는 가정 하에 키보드 입력하는 횟수에만 초점을 맞추고 풀이를 해보자.

 

키보드 입력 횟수 구하기

예시 1을 다뤄보면 총 8번의 키보드 입력이 필요하다. []에 들어간 문자들이 키보드 입력하는 구간이다. 

[g]oodbye  : 1
[h]e[a]ven  : 2
[h]e[l]l        : 2
[h]e[l]l[0]   : 3 
> 총 8번 키보드 입력

특징을 잘 살펴보면 키보드를 입력하는 경우의 수는 총 3가지로 따져 볼 수 있다.

1. 맨 처음 문자를 입력할 때
2. 자식 노드의 갯수가 2개 이상일 때
3. 중간 노드가 terminal(마지막 문자)일 때

3번 예시로는 hell[o]라는 문자를 입력할 경우 hell로 종료되는 문자가 있기 때문에 [o]를 한 번 더 입력해줘야 하므로 카운트를 해줘야한다.

public int autoModule(String word) { 
	TrieNode trieNode = this;
	int cnt=0;
	for(int i=0; i<word.length(); i++) {
		char c= word.charAt(i);
		TrieNode node = trieNode.childNode.get(c);
		// 문자 시작 키보드 입력
		if(i==0) {
			cnt++;
		}
		// 중간 terminal 노드 || 경우의 수가 2가지 이상이면 키보드 입력
		else if(trieNode.terminal || trieNode.childNode.size()>1) {
			cnt++;
		}

		trieNode = node;
	}
	return cnt;
}

 

이렇게 모든 문자들을 대입하여 각 문자열에 필요한 키보드 입력 횟수를 구한 다음 모든 문자열 갯수로 나눠주면 된다. 해당 문제는 입력 종료가 따로 없으므로 try~catch문으로 예외처리를 해주면 된다.

 

위의 로직을 시뮬레이션을 돌려보면 빨간 동그라미로 그려진 지점에서 cnt++을 하는 것을 알 수 있다.

• 맨 처음 문자를 입력할 때 [H]
• 자식 노드의 갯수가 2개 이상일 떄 [L], [A]
• 중간 노드가 terminal노드 일 때 [L] > [O]
  • HELLO를 탐색하는 과정에서 4번째 [L]을 탐색하는 구간에서 cnt된다. 

트라이 예시

 

 

풀이 코드 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Main {
	static class TrieNode{
		Map<Character, TrieNode> childNode = new HashMap<>();
		boolean terminal;
		
		public TrieNode(){
			/* no-op */
		}
		
		public void insert(String word) {
			TrieNode trieNode = this;
			for(int i=0; i<word.length(); i++) {
				char c = word.charAt(i);
				
				trieNode.childNode.putIfAbsent(c, new TrieNode());
				trieNode = trieNode.childNode.get(c);
				
				if(i==word.length()-1) {
					trieNode.terminal = true;
				}
			}
		}
		
		public int autoModule(String word) { 
			TrieNode trieNode = this;
			int cnt=0;
			for(int i=0; i<word.length(); i++) {
				char c= word.charAt(i);
				TrieNode node = trieNode.childNode.get(c);
				if(i==0) {
					cnt++;
				}
				else if(trieNode.terminal || trieNode.childNode.size()>1) {
					cnt++;
				}
				trieNode = node;
			}
			return cnt;
		}
	}
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));	
		String line;
		while((line = br.readLine())!=null) {
			try {
				int n = Integer.parseInt(line);
				List<String> inputData = new ArrayList<>();
				TrieNode trie = new TrieNode();
				for(int i=0; i<n; i++) {
					String str = br.readLine();
					inputData.add(str);
					trie.insert(str);
				}
				double res=0;
				for(String str : inputData) {
					res+= trie.autoModule(str);	
				}
				System.out.println(String.format("%.2f",res/inputData.size()));
			}catch(NumberFormatException e) {
				return;
			}
		}
	}
}