가사 검색 풀이
처음보는 트라이 구조 자료구조를 이용해 문제를 풀어야해서 매우 감이 안잡혔었습니다. 역시 이런문제는 한번 맞아봐야 다음부터 제대로 풀 수 있습니다. 제 기억으로 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]) 는 정규식을 이용한 것으로 알파벳을 제외한 다른 문자는 빼주는 코드입니다.