가사검색
문제
[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]
친구들로부터 천재 프로그래머로 불리는 프로도는 음악을 하는 친구로부터 자신이 좋아하는 노래 가사에 사용된 단어들 중에 특정 키워드가 몇 개 포함되어 있는지 궁금하니 프로그램으로 개발해 달라는 제안을 받았습니다.
그 제안 사항 중, 키워드는 와일드카드 문자중 하나인 '?'가 포함된 패턴 형태의 문자열을 뜻합니다. 와일드카드 문자인 '?'는 글자 하나를 의미하며, 어떤 문자에도 매치된다고 가정합니다. 예를 들어 "fro??"는 "frodo", "front", "frost" 등에 매치되지만 "frame", "frozen"에는 매치되지 않습니다.
가사에 사용된 모든 단어들이 담긴 배열 words와 찾고자 하는 키워드가 담긴 배열 queries가 주어질 때, 각 키워드 별로 매치된 단어가 몇 개인지 순서대로 배열에 담아 반환하도록 solution 함수를 완성해 주세요.
가사 단어 제한사항
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??"('?'가 양쪽에 있음)는 불가능한 키워드입니다.
예시
## words queries result
["frodo", "front", "frost", "frozen", "frame", "kakao"] ["fro??", "????o", "fr???", "fro???", "pro?"] [3, 2, 4, 1, 0]
풀이
처음 문제를 풀 때는 words 안에 있는 문자의 오른쪽, 왼쪽을 시작으로 ? 을 추가하면서 queries와 일치하는지 확인해가면 문제를 풀었다. 모든 문제가 정상적으로 풀렸지만 효율성에서 실패가 떴다.
String 검색 문제는 trie 자료구조를 사용하여 풀면 편하다. (공간 복잡도를 확 줄일 수 있다.) 이 문제는 일반적으로 단어를 검색하는 문제는 아니다. ? 을 포함하고 있고 여기에는 어떠한 알파벳이 들어가도 되기 때문이다. 그래서 풀고자하는 방식은 ?가 나오기 전까지 검색을 진행하고, ? 가 나오면 단어의 length가 일치하는지 확인하는 것이다. 예를들어 “fro??”이면, words 배열에서 “fro”을 가진 5자리의 모든 단어가 올 수 있다. Trie은 줄기를 타고 내려가면서 검색하기 때문에 node마다 그 node 아래에 있는 단어 길이의 개수를 저장해두면 재검색 없이 그때 그때 바로 return할 수 있다.
Trie에서, 각 노드를 만들 때마다 각 노드에 현재 단어의 length을 계속 넣어주고 같은 것이 있으면 +1을 해주면 된다. 검색을 할 때는 ?을 만났을 때, 그 바로 직전 알파벳에 들어 있는 단어 길이의 개수를 출력하면 된다.
def solution(words, queries):
# trie 구조 이용
answer = []
class Trie():
def __init__(self):
self.head = {}
def add(self, s):
now = self.head
# ?????와 같은 것을 방지 (root에도 string length 저장)
if len(s) in now:
now[len(s)] += 1
else:
now[len(s)] = 1
for ss in s:
if ss not in now:
now[ss] = {}
# 같은 문자열 길이가 있으면 +1 없으면 새로 만듦
if len(s) in now[ss]:
now[ss][len(s)] += 1
else:
now[ss][len(s)] = 1
now = now[ss]
def search(self, s):
now = self.head
for ss in s:
# ?을 만나면 단어 length가 같은것 return
if ss == '?':
if len(s) in now:
return now[len(s)]
else:
return 0
# 아예 없는 문자열을 만나면 False
if ss not in now:
return 0
now = now[ss]
# 정방향
trie = Trie()
for word in words:
trie.add(word)
# 역방향
rTrie = Trie()
for word in words:
rTrie.add(word[::-1])
for q in queries:
if q[0] == '?':
answer.append(rTrie.search(q[::-1]))
else:
answer.append(trie.search(q))
return answer
효율성 테스트 3번 반례
효율성 3번에서 계속 시간초과가 나와서 검색을 하다가 3번은 모두 물음표가 들어가 있는 “?????”와 같은 형태라고 한다. 따져보니 trie의 root 부분에는 단어길이가 저장되어 있지 않아서 시간초과가 나는 것 같았다. add 메서드 쪽에 아래와 같이 맨처음에 초기화를 해준 뒤, node을 만들어가면 된다.
# ...
# ?????와 같은 것을 방지 (root에도 string length 저장)
if len(s) in now:
now[len(s)] += 1
else:
now[len(s)] = 1
# ...