[python] 가사 검색(2020 kakao blind recruitment, 프로그래머스)
Problem
[문제설명]
본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.친구들로부터 천재 프로그래머로 불리는 프로도는 음악을 하는 친구로부터 자신이 좋아하는 노래 가사에 사용된 단어들 중에 특정 키워드가 몇 개 포함되어 있는지 궁금하니 프로그램으로 개발해 달라는 제안을 받았습니다.
그 제안 사항 중, 키워드는 와일드카드 문자중 하나인 ‘?’가 포함된 패턴 형태의 문자열을 뜻합니다. 와일드카드 문자인 ‘?’는 글자 하나를 의미하며, 어떤 문자에도 매치된다고 가정합니다. 예를 들어 “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??”(‘?’가 양쪽에 있음)는 불가능한 키워드입니다.
문제 링크 : 프로그래머스 가사 검색
<Try>
# 두 단어의 일치 여부 확인
def match(q, w):
N = 0
# '?'이 접두사로 나올 때
if q.startswith("?"):
for i in range(len(q)):
if q[i] != "?":
N = i
break
for letter1, letter2 in zip(q[N:], w[N:]):
if letter1 != letter2:
return False
# '?'이 접미사로 나올 때
else:
for i in range(len(q)):
if q[len(q) - i - 1] != "?":
N = i
break
for letter1, letter2 in zip(q[:len(q) - N], w[:len(q) - N]):
if letter1 != letter2:
return False
return True
# 쿼리에 있는 단어에 대하여 words 중 몇 개의 단어와 일치하는지 카운팅
def counting(q, words):
cnt = 0
for w in words:
if len(w) != len(q):
continue
if match(q, w):
cnt += 1
return cnt
def solution(words, queries):
answer = []
for q in queries:
answer.append(counting(q, words))
return answer
처음에 이 문제를 봤을 때 선형적으로 검색해보면 풀릴 것 같아서 단순하다고 생각했다.
먼저 match 함수에서 ‘?”이 접두사로 올 때, 접미사로 올 때로 나누었다. ‘?’이 나오는게 멈춘다면 그 때 인덱스를 기억해두어 그 다음부터 문자가 일치하는지 확인했다.
counting 함수에서는 쿼리에 있는 한 단어에 대하여 words의 몇 개의 단어들과 일치하는지 수를 센다. 길이가 갈을 때만 match 함수로 보내어 일치 여부를 확인한다.
결과적으로 정확성 테스트는 통과하였으나, 효율성 테스트에서 실패가 떴다. 이 문제에서 요구하는 것이 따로 있었는데 그것은 Trie라는 자료구조이다.
<Solution>
from collections import defaultdict
# Trie 자료구조안에 위치하고 있는 노드 정의
class Node(object):
def __init__(self, key, passnumber=None, isEnd=None):
self.key = key
# 해당 노드를 지나간 길이 별 단어 갯수
self.passnumber = defaultdict(int)
self.isEnd = False
self.children = {}
# Trie 자료구조
class Trie(object):
def __init__(self):
self.head = Node(None)
# 새로운 단어 추가
def insert(self, string):
curr_node = self.head
curr_node.passnumber[len(string)] += 1
for char in string:
if char not in curr_node.children:
curr_node.children[char] = Node(char)
curr_node = curr_node.children[char]
curr_node.passnumber[len(string)] += 1
curr_node.isEnd = True
# 쿼리 단어에 일치하는 단어 수 반환
def search(self, query):
curr_node = self.head
for q in query:
if q == "?":
break
if q in curr_node.children:
curr_node = curr_node.children[q]
else:
return 0
return curr_node.passnumber[len(query)]
def solution(words, queries):
trie = Trie()
# "?"가 앞에 있는 단어들을 뒤에서 부터 검사하기 위한 r_trie
r_trie = Trie()
# 단어 reverse
r_words = [w[::-1] for w in words]
# 중복되는 쿼리를 담기 위한 딕셔너리
dic = {}
answer = []
for word in words:
trie.insert(word)
for word in r_words:
r_trie.insert(word)
for query in queries:
if query in dic:
answer.append(dic[query])
continue
if query.endswith("?"):
result = trie.search(query)
answer.append(result)
dic["query"] = result
else:
result = r_trie.search(query[::-1])
answer.append(result)
dic["query"] = result
return answer
trie는 단어의 각 문자들을 하나의 노드로 만들어 트리를 구성하도록 한 자료구조이다.
trie를 생성해야 하기 때문에 적은 수의 검색에서는 선형 검색이 유리할 수 있지만, 검색해야할 수가 많아질수록 trie의 효율이 높아진다.
이 문제에서 trie를 생성할 때 두 가지 중점 요소가 있다.
- ’?’이 접두사로 올 경우를 대비해 단어를 역순으로 넣은 r_trie를 따로 생성한다.
- 단어 검색 시 빠른 검색을 위해 trie를 구성할 때, 특정 노드를 지난 단어의 길이별 passnumber를 저장해 둔다.
trie 자료구조의 시간 복잡도는 다음과 같다.
제일 긴 문자열의 길이를 L, 문자열의 총 수를 M이라 할 때, 생성시 시간복잡도는 O(M*L), 검색시 시간복잡도는 O(L)이다.
