💻 링크
https://school.programmers.co.kr/learn/courses/30/lessons/60060
📖 문제 해결
이진 탐색을 이용하여 각 쿼리마다 매치되는 단어의 개수를 계산해 줌으로써 해결할 수 있는 문제입니다. 먼저 words 내의 단어들에 대해서 길이 별로 나누어 리스트에 담은 후 정렬을 수행해 줍니다. 그리고 queries 내의 각 쿼리들에 대하여 순서대로 이진 탐색을 진행하며 매치된 단어의 수를 계산해 주는 방식으로 문제를 해결할 수 있습니다.
예를 들어 "fro??"라는 쿼리가 들어왔다고 가정해 보면, "fro??"는 길이가 5이기 때문에 길이가 5인 단어 리스트에서 "fro"로 시작하는 단어들을 모두 찾으면 됩니다. 이때 "fro"로 시작하는 길이가 5인 단어의 개수는 지난 게시물에서 다루었던 count_by_range()함수를 이용하여 "frozz"가 들어가는 위치 - "froaa"가 들어가는 위치를 계산함으로써 매치된 단어의 수를 구할 수 있습니다.
또한 "????o"처럼 와일드카드인 "?"가 위와 같이 접미사로 들어오는 경우가 아닌 접두사로 들어오는 경우에 대해서도 고려하여야 합니다. 접두사에 와일드카드가 들어오는 경우에 대해서는, 쿼리와 단어들을 모두 뒤집어서, 마치 접미사에 와일드카드가 들어온 경우처럼 문제를 풀면 됩니다. 이 경우를 고려하기 위하여 주어진 쿼리인 "????o"를 "o????"로 뒤집고, words 내의 단어들도 뒤집은 후 길이별로 나누어 reversed_array 리스트에 담아주고 오름차순으로 정렬해 줍니다. 그 후 접미사에 와일드카드가 들어왔던 경우와 동일하게 count_by_range()함수를 이용하여 "oaaaa"가 들어가는 위치 - "ozzzz"가 들어가는 위치를 계산함으로써 매치된 단어의 수를 계산해 주었습니다.
from bisect import bisect_left, bisect_right
# 값이 [left_value, right_value]인 데이터의 개수를 반환하는 함수
def count_by_range(a, left_value, right_value):
right_index = bisect_right(a, right_value)
left_index = bisect_left(a, left_value)
return right_index - left_index
# 모든 단어를 길이마다 나누어서 저장하기 위한 리스트
array = [[] for _ in range(10001)]
# 모든 단어를 길이마다 나누어서 뒤집어 저장하기 위한 리스트
reversed_array = [[] for _ in range(10001)]
def solution(words, queries):
answer = []
# 모든 단어를 접미사 와일드 카드 배열, 접두사 와일드 카드 배열에 각각 삽입
for word in words:
# 단어를 삽입
array[len(word)].append(word)
# 단어를 뒤집어서 삽입
reversed_array[len(word)].append(word[::-1])
# 이진 탐색을 수행하기 위해 각 단어 리스트 정렬 수행
for i in range(10001):
array[i].sort()
reversed_array[i].sort()
# 쿼리를 하나씩 확인하며 처리
for q in queries:
# 접미사에 와일드카드가 붙은 경우
if q[0] != '?':
res = count_by_range(array[len(q)], q.replace('?', 'a'), q.replace('?','z'))
# 접두사에 와일드카드가 붙은 경우
else:
res = count_by_range(reversed_array[len(q)], q[::-1].replace('?', 'a'), q[::-1].replace('?','z'))
# 검색된 단어의 개수를 저장
answer.append(res)
return answer