가사 검색 풀이
처음보는 트라이 구조 자료구조를 이용해 문제를 풀어야해서 매우 감이 안잡혔었습니다. 역시 이런문제는 한번 맞아봐야 다음부터 제대로 풀 수 있습니다. 제 기억으로 2021 공채 시험에서도 트라이 구조를 이용한 문제가 3번인가 4번으로 나왔었는데 꼭 이해하고 넘어 가시길 바랍니다.
코드
import re
def solution(words, queries):
answer = []
trees = [Trie() for _ in range(10000)]
inv_trees = [Trie() for _ in range(10000)]
for word in words :
trees[len(word)-1].insert(word)
inv_trees[len(word)-1].insert(word[::-1])
for query in queries :
if query[0] == '?' :
answer.append(inv_trees[len(query)-1].query(re.sub('[^a-z]', '', query[::-1])))
else :
answer.append(trees[len(query)-1].query(re.sub('[^a-z]', '', query)))
return answer
class TrieNode:
def __init__(self, char):
self.char = char
self.counter = 0
self.children = {}
class Trie(object):
def __init__(self):
self.root = TrieNode("")
def insert(self, word):
node = self.root
for char in word:
node.counter += 1
if char in node.children:
node = node.children[char]
else:
new_node = TrieNode(char)
node.children[char] = new_node
node = new_node
node.counter += 1
def query(self, word) :
node = self.root
for char in word :
if char not in node.children : return 0
node = node.children[char]
return node.counter
문제에 관하여
저는 학교에서 트라이 구조를 배우지 않아서 이 문제를 풀며 처음 접하게 되었습니다. 트라이구조는 자식이 2개가아닌 3개 4개 혹은 그이상을 가질 수 있는 트리 자료구조 입니다. 검색을 통해 알게된 사실인데 이 자료구조의 일종이 B tree
, B+ tree
등등 검색엔진에 이용되는 자료구조입니다. 트라이 자료구조를 이용하지 않으면 절대로 효율성 테스트를 통과할 수 없습니다. 이 문제는 감이 안잡혀서 카카오 공식 해설을 보며 풀었으니 이점 참고해 주시길 바랍니다.
일단 이 문제는 제한사항을 봐야 합니다.
가사 단어 제한사항
words
의 길이(가사 단어의 개수)는 2 이상 100,000 이하입니다.- 각 가사 단어의 길이는 1 이상 10,000 이하로 빈 문자열인 경우는 없습니다.
- 전체 가사 단어 길이의 합은 2 이상 1,000,000 이하입니다.
- 가사에 동일 단어가 여러 번 나올 경우 중복을 제거하고
words
에는 하나로만 제공됩니다.- 각 가사 단어는 오직 알파벳 소문자로만 구성되어 있으며, 특수문자나 숫자는 포함하지 않는 것으로 가정합니다.
검색 키워드 제한사항
queries
의 길이(검색 키워드 개수)는 2 이상 100,000 이하입니다.각 검색 키워드의 길이는 1 이상 10,000 이하로 빈 문자열인 경우는 없습니다.
전체 검색 키워드 길이의 합은 2 이상 1,000,000 이하입니다.
검색 키워드는 중복될 수도 있습니다.
각 검색 키워드는 오직 알파벳 소문자와 와일드카드 문자인
'?'
로만 구성되어 있으며, 특수문자나 숫자는 포함하지 않는 것으로 가정합니다.검색 키워드는 와일드카드 문자인
'?'
가 하나 이상 포함돼 있으며,
'?'
는 각 검색 키워드의 접두사 아니면 접미사 중 하나로만 주어집니다.
- 예를 들어
"??odo"
,"fro??"
,"?????"
는 가능한 키워드입니다.- 반면에
"frodo"
('?'
가 없음),"fr?do"
('?'
가 중간에 있음),"?ro??"
('?'
가 양쪽에 있음)는 불가능한 키워드입니다.
한번 중요한 액기스만 뽑아 봅시다.
word
와query
의 각 원소의 길이는 1~10000 이다.query
의?
는 가운데 못오고 앞이나 뒤에만 붙을 수 있다.'???ab'
,'ab???'
이런 식으로
여기까지하고 우선 우리가 쓸 트라이 자료구조를 한번 봅시다.
트라이 트리의 삽입 과정입니다. 눈여겨 봐야할 부분은
각 노드에 자식의 갯수 update
새로운 단어가 없을시 노드 추가하고 현재 노드를 추가한 노드로 바꿈
이 두가지 입니다.
이렇게 해놓으면 query
의 단어 'abc???'
가 주어졌을 때, 줄기를 타고 내려간 다음 노드 c
의 자식 갯수를 return
해주면 됩니다.
자, 이제 자세히 문제의 제한사항을 봅시다.
제한 사항
word
의 길이가 1~10000 입니다. 그리고query
의 길이도 1~10000 입니다. 즉query
가'abc??'
일 때,'abcacc'
나'abcd'
처럼query
글자길이와 틀린 단어를 갯수에 포함시키면 안됩니다. 따라서 한 단어 트라이 트리, 두 단어 트라이 트리, …, 만개 단어 트라이트리로 총 10000개의 트리를 만들어주어야 합니다.
트라이 트리는 여느 트리처럼
root
부터 타고 들어가 탐색을 진행합니다. 하지만 쿼리중에는 와일드카드가 앞에달린 ('???abc'
) 경우가 있습니다. 그래서 이런 경우를 대비하여 단어가 거꾸로 뒤집힌 트라이 트리 또한 만들어 주어야 합니다. 당연히 탐색을 할 때query
또한 뒤집어서 탐색을 해야합니다.'???abc'
->'cba'
로 탐색 진행
코드를 봅시다.
Trie Tree
class TrieNode:
def __init__(self, char):
self.char = char # 단어하나
self.counter = 0 # 자식 갯수
self.children = {} # 자식들
class Trie(object):
def __init__(self):
self.root = TrieNode("")
def insert(self, word):
node = self.root
for char in word:
node.counter += 1 # 중복된 단어는 없으므로 어차피 새로운 자식이 하나 추가됨. 그래서 for문마다 1 증가
if char in node.children:
node = node.children[char]
else:
new_node = TrieNode(char)
node.children[char] = new_node
node = new_node
node.counter += 1
def query(self, word) :
node = self.root
for char in word :
if char not in node.children : return 0 # 없는 단어
node = node.children[char]
return node.counter # 노드의 자식 갯수 반환
트라이 구조 움짤을 봤다면 쉽게 이해할 수 있을꺼라 생각합니다.
Solution
import re
def solution(words, queries):
answer = []
trees = [Trie() for _ in range(10000)] # 일반 단어 트리 10000개
inv_trees = [Trie() for _ in range(10000)] #거꾸로된 단어트리 10000개
for word in words : # 단어 갯수에 맞는 트리에다가 삽입
trees[len(word)-1].insert(word)
inv_trees[len(word)-1].insert(word[::-1])
for query in queries :
if query[0] == '?' :
answer.append(inv_trees[len(query)-1].query(re.sub('[^a-z]', '', query[::-1])))
else :
answer.append(trees[len(query)-1].query(re.sub('[^a-z]', '', query)))
return answer
나머지는 쉬우므로 query
부분만 봅시다. query
의 첫 시작이 '?'
라면 거꾸로된 트리에서 찾아야합니다.
re.sub('[^a-z]', '', query[::-1])
는 정규식을 이용한 것으로 알파벳을 제외한 다른 문자는 빼주는 코드입니다.