[백준 / BOJ] 18119 단어 암기 - Trie

문제

출처 : www.acmicpc.net/problem/18119

18119번: 단어 암기

준석이가 영어단어를 외울려고한다.

사전에 N가지 단어가적혀있으며, 모든 단어는 소문자로만 이루어져있다.

준석이는 처음에 모든 알파벳을알고있지만, 쿼리가 주어질때마다 알파벳을 까먹을수도 까먹은 단어를 기억할수도있다.

 

단어장에 적혀있는 N개의 단어와 M번의 쿼리 가 주어졌을때, 각 쿼리마다 준석이가 기억하는 단어의 개수를 출력하는 문제다.

 

풀이

최악의 경우,

N = 10000 이때 각 단어의 길이는 최대 1000

M = 5*10000

이라서, 완전탐색으로 풀려하면, M * N * 단어의길이 가 되서 시간초과가 나온다.

 

처음생각은 Trie로 최장 문자열 길이만큼 비교해주는거였는데, Trie로 풀었을때 메모리 초과가 나왔다. (메모리 초과를 해결했어도 시간초과가 나왔을듯)

 

일반적인 Trie로 풀려해도 시간초과가 나오는데, 최악의경우

한번의 쿼리마다 탐색 횟수는 26*1000 = 26000 이다. (알파벳횟수 * 최장문자길이) 이때, 쿼리횟수가 5*10000이므로, 약 13억번 반복한다.

 

Trie 구조를 만들때, 약간의 트릭이 필요했다.

아이디어는, 해당 단어에 속해있는 모든 알파벳의 종류를 알고있으면, 해당 단어를 알고있다. 에서 나왔는데, 이 말은, 해당 단어에 속해있는 알파벳의 종류들을 알수있다면, 그 단어의 길이만큼 Trie구조를 늘려줄필요없이, 단어에 속한 알파벳종류만큼만 늘려주면 된다. 라고 생각할수있다. 

예를들어, 축약전 단어장이 다음과 같다고하자.

 

초기 단어장 : 

apple

banana

pencil

alphabet

aaaaa

위 단어장을 축약해서 저장해도 해당 단어를 알고있는지 알수있다.

 

축약 단어장 :

appl

ban

pencil

alphbet

a

축약 단어장을 만들면 최장 문자열의 길이를 1000에서 26으로 줄일수있다. 따라서, 한번의 쿼리당 탐색횟수가 26*26으로 획기적으로 짧아진다.

 

이렇게 축약해서 저장할때 주의할점이 있는데, 단어가 중복해서 나올수있다는것이다. 

예를들어, banana 와 ban은 다른 단어지만, 축약결과가 같다. 따라서, Trie구조에서 단어의 끝을 알리는지점에 해당 지점에서 끝나는 단어의 갯수를 저장해줘야한다.

b -> a -> n(2) 이런식으로

 

나머지 구현은 기본 Trie처럼 하면된다.

 

이게 정해는 아닌듯하다.. 뱅뱅 돌려서 풀은듯한 느낌..

소스코드

https://github.com/devxb/JJUNalgo/blob/master/18119%20%EB%8B%A8%EC%96%B4%20%EC%95%94%EA%B8%B0/main.cpp

devxb/JJUNalgo