문제
https://www.acmicpc.net/problem/5670
입력
입력은 여러 개의 테스트 케이스로 이루어져 있다.
각 테스트 케이스의 첫째 줄에 사전에 속한 단어의 개수 N이 주어지며, 이어서 N개의 줄에 1~80글자인 영어 소문자로만 이루어진 단어가 하나씩 주어진다. 이 단어들로 사전이 구성되어 있으며, 똑같은 단어는 두 번 주어지지 않는다.
출력
각 테스트 케이스마다 한 줄에 걸쳐 문제의 정답을 소수점 둘째 자리까지 반올림하여 출력한다.
풀이
제한조건
- (1 ≤ N ≤ 105)
- 1~80글자인 영어 소문자로만 이루어진 단어
- 똑같은 단어는 두 번 주어지지 않는다.
- 각 테스트 케이스마다 입력으로 주어지는 단어의 길이 총합은 최대 106이다.
접근방법
'트라이'
테스트케이스의 수가 몇 개인지 알 수 없다.
또한, 단어의 개수가 10^5 까지로, 단순하게 접근한다면, 시간초과를 만날 확률이 높다.
예시의 자동 완성이 되는 과정을 살펴보면, 마치 트라이 구조와 동일함을 알 수 있다.
트라이 구조를 사용해 아래와 같이 접근해보자.
(트라이 : https://velog.io/@hyeokkr/Trie)
1. 입력단어를 모두 트라이 구조로 생성한다.
2. 각 입력 단어마다, 몇 번의 입력이 필요한지 계산한다.
3. 평균 횟수를 구한다.1. 입력단어를 모두 트라이 구조로 생성한다.
모든 입력단어를 트라이 구조에 넣어보자.
hello
hell
heaven
goodbye위의 단어들이 입력으로 주어진다면, 생성한 트라이 구조는 아래와 같이 그려진다.
(색이 있는 원은 마지막을 나타냄.)
이때, 입력에서 단순하게 insert만 하는게 아니라, 나중에 하위단어가 얼마나 있는지 편하게 확인하기 위해서 count라는 변수를 추가적으로 두고, 하위단어의 갯수가 몇 개인지를 기록해 두자.
static class TrieNode {
public Map<Character, TrieNode> childNodes = new HashMap(); // 하위 문자 관리
public int count; // 하위 단어들의 수
public boolean isLast; // 마지막 문자인가?
}
static 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;
}
}2. 각 입력 단어마다, 몇 번의 입력이 필요한지 계산한다.
이제 입력단어 마다 입력횟수를 계산해야하는데,
- 특정 가지로 뻗었을 때, 하위 단어가 1개밖에 없다면 해당 시점에서 완료되었다고 볼 수 있다.
그림에서 root에서 g 방향으로 첫 입력을 했을 때, 하위 단어가 해당 단어 밖에 없으므로 1번의 입력으로 자동완성이 가능하다.
- 하위단어가 2개 이상이라면, 마지막 단어인지 체크하며 count를 증가시키며 계속 하위로 내려가 본다.
그림을 기준으로 본다면, h를 봤을 때, 하위 단어가 여러개 있다.
하지만, 해당 글자가 마지막이 아니고, 공통적인 부분이므로, 추가적인 카운트 증가없이 하위로 탐색한다. - 문제의 조건에 따라 첫 입력은 자동완성 되지 않으므로, root에서 이어진 알파벳이 1개인 경우도 count를 증가시켜 줘야 한다.
he
hi
h
-> h는 자동완성 되지 않는다.!int getMinTypingCount(String word) {
TrieNode node = this.root;
int length = word.length();
int count = 0;
if (node.childNodes.size() == 1)
count++;
for (int i = 0; i < length; i++) {
// 남은 하위 단어가 1개라면, 현재 입력으로 결정된다
if (node.count == 1)
break;
if (node.childNodes.size() > 1 || node.isLast)
count++;
node = node.childNodes.get(word.charAt(i));
}
return count;
코드
import java.io.BufferedReader;
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 {
public Map<Character, TrieNode> childNodes = new HashMap(); // 하위 문자 관리
public int count; // 하위 단어들의 수
public boolean isLast; // 마지막 문자인가?
}
static 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 count = 0;
if (node.childNodes.size() == 1)
count++;
for (int i = 0; i < length; i++) {
// 남은 하위 단어가 1개라면, 현재 입력으로 결정된다
if (node.count == 1)
break;
if (node.childNodes.size() > 1 || node.isLast)
count++;
node = node.childNodes.get(word.charAt(i));
}
return count;
}
}
static int N;
public static void main(String[] args) throws Exception {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
String input = "";
while ((input = in.readLine()) != null) {
N = stoi(input);
Trie myTrie = new Trie();
List<String> list = new ArrayList<>();
for (int i = 0; i < N; ++i) {
String s = in.readLine();
myTrie.insert(s);
list.add(s);
}
int answer = 0;
for (String str : list)
answer += myTrie.getMinTypingCount(str);
System.out.printf("%.2f\n", Math.round(((double)answer / (double)list.size()) * 100) * 0.01);
}
}
public static int stoi(String s) {
return Integer.parseInt(s);
}
}