🗃️문제 설명
[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]
친구들로부터 천재 프로그래머로 불리는 "프로도"는 음악을 하는 친구로부터 자신이 좋아하는 노래 가사에 사용된 단어들 중에 특정 키워드가 몇 개 포함되어 있는지 궁금하니 프로그램으로 개발해 달라는 제안을 받았습니다.
그 제안 사항 중, 키워드는 와일드카드 문자중 하나인 '?'가 포함된 패턴 형태의 문자열을 뜻합니다. 와일드카드 문자인 '?'는 글자 하나를 의미하며, 어떤 문자에도 매치된다고 가정합니다. 예를 들어 "fro??"는 "frodo", "front", "frost" 등에 매치되지만 "frame","frozen"에는 매치되지 않습니다.
가사에 사용된 모든 단어들이 담긴 배열 words와 찾고자 하는 키워드가 담긴 배열 queries가 주어질 때, 각 키워드 별로 매치된 단어가 몇 개인지 순서대로 배열에 담아 반환하도록 solution 함수를 완성해 주세요.
🖥️코드
class Node:
def __init__(self, key):
self.key = key
self.match = 0 # 여기서 중요한 것은 ?가 글자 하나에 매칭이 되므로 문자열의 길이가 일치 여부보다도 중요
self.children = {}
class Trie:
def __init__(self):
self.head = Node(None)
def insert(self, string):
curr = self.head
for char in string:
curr.match += 1
if char not in curr.children:
curr.children[char] = Node(char)
curr = curr.children[char]
def startswith(self, string):
curr = self.head
for char in string:
if char == "?":
break
if char in curr.children:
curr = curr.children[char]
else:
return 0
return curr.match
def solution(words, queries):
answer = []
tries = {}
reverse_tries = {}
for word in words:
size = len(word)
if size not in tries:
tries[size] = Trie() # 단어 길이별로 트라이 자료구조를 구축
reverse_tries[size] = Trie()
tries[size].insert(word)
reverse_tries[size].insert(word[::-1])
for query in queries:
size = len(query)
if size in tries:
if query[0] != "?":
trie = tries[size]
answer.append(trie.startswith(query))
else:
trie = reverse_tries[size]
answer.append(trie.startswith(query[::-1]))
else:
answer.append(0)
return answer👉많이 어려웠다. 트라이 자료구조를 모르는 상태였고 처음엔 BST를 사용해서 각 문자열별로 트리를 구성해 탐색을 하려고 했으나 뜻대로 되지 않았다.
👉트라이 자료구조의 기본 틀 정돈 숙지하는게 좋을 것 같다.
