[Python] 가사검색

프로그래머스 가사검색

문제 설명

친구들로부터 천재 프로그래머로 불리는 “프로도”는 음악을 하는 친구로부터 자신이 좋아하는 노래 가사에 사용된 단어들 중에 특정 키워드가 몇 개 포함되어 있는지 궁금하니 프로그램으로 개발해 달라는 제안을 받았습니다. 그 제안 사항 중, 키워드는 와일드카드 문자중 하나인 ‘?’가 포함된 패턴 형태의 문자열을 뜻합니다. 와일드카드 문자인 ‘?’는 글자 하나를 의미하며, 어떤 문자에도 매치된다고 가정합니다. 예를 들어 “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??”(‘?’가 양쪽에 있음)는 불가능한 키워드입니다.

입출력 예

가사검색1

입출력 예 설명

“fro??”는 “frodo”, “front”, “frost”에 매치되므로 3입니다.
”????o”는 “frodo”, “kakao”에 매치되므로 2입니다.
“fr???”는 “frodo”, “front”, “frost”, “frame”에 매치되므로 4입니다.
“fro???”는 “frozen”에 매치되므로 1입니다.
“pro?”는 매치되는 가사 단어가 없으므로 0 입니다.

풀이

효율성 테스트를 통과하는것이 핵심인 문제입니다. Trie자료구조 혹은 이진탐색을 사용하지 않으면 효율성 테스트를 통과하지 못합니다. 이진탐색을 통해 풀어보겠습니다. 핵심은, ?를 a와 z로 바꾼 후 그 사이에 있는 인덱스들의 개수를 구하면 됩니다. 이때 특정 구간의 개수를 구하는 count_by_range라는 함수를 미리 구현합니다.

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

가사검색2

bisect_right(a, x)와 bisect_left(a, x)는 파이썬에서 이진탐색을 구현한 모듈로, 정렬된 순서 a에서 x를 삽입할 경우 가장 오른쪽/왼쪽 위치를 반환합니다. 두 위치의 차이는 그 사이 원소들의 개수에 해당합니다.

“fro??”를 예로 들면 count_by_range(words,”froaa”, “frozz”)의 결과값은 3이됩니다. 왜냐하면 words는 현재 [‘frodo’, ‘front’, ‘frost’, ‘frame’, ‘kakao’]이고(길이가 6인 frozen은 제외) froaa는 첫번째, frozz는 4번째로 그 사이에 있는 원소는 총 3개입니다.

본격적으로 문제를 풀어보겠습니다.

제일 먼저 words들을 각 길이별로 각각 나눕니다.
- 쿼리의 길이별로 각각의 다른 words를 사용해야 합니다.
query가 ?로 시작하는 경우와 ?로 시작하지 않는 경우를 구분해야 됩니다.
- 예를 들어, ?aa 쿼리의 경우 words가 ['aaa','cbb','dbb']이면, aaa ~ zaa까지 모든 단어가 해당됨으로 3이 됩니다. 하지만 실제 쿼리에 해당하는 단어는 aaa뿐입니다. 이를 해결하기 위해서는 query와 word도 모두 거꾸로 만들어야 됩니다. 이경우 query는 aa?이고 words는 ['aaa','bbc','bbd'] 입니다. aaa한개만 추출되고 이능 우리가 원하는 결과값입니다.
- 즉 query도 거꾸로 받고, words로 거꾸로 변환하여 reversed_data라는 이중리스트를 새로 생성합니다.
차례로 query를 받으며 count_by_range함수를 통해 값이 query.replace('?','a')와 query.replace('?','z') 사이인 원소들의 개수를 구합니다.

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

data = [[] for x in range(10001)]
reversed_data = [[] for x in range(10001)]

def solution(words, queries):
    result = []
    for word in words:
        data[len(word)].append(word)
        reversed_data[len(word)].append(word[::-1])

    for i in range(10001):
        data[i].sort()
        reversed_data[i].sort()

    for query in queries:
        if query[0] != "?":
            answer = count_by_range(data[len(query)], query.replace('?','a'), query.replace('?','z'))
        else:
            answer = count_by_range(reversed_data[len(query)], query[::-1].replace('?','a'), query[::-1].replace('?','z'))
        result.append(answer)
    return result