[프로그래머스] 가사 검색 파이썬 풀이

가사 검색 (Lv.4)

요구사항

• 정확성과 효율성 테스트 각각 점수가 있음 (시간 복잡도에 유의하여 문제를 해결해야 함)
• 가사에 사용된 모든 단어들이 담긴 배열 words,
• 찾을 키워드가 담긴 배열 queries,
• 각 키워드 별로 매치된 단어의 개수를 순서대로 배열에 담아 반환
• 키워드에는 문자 하나를 의미하는 와일드 카드 문자 '?'가 포함되어 있다.
• 각 검색 키워드는 오직 알파벳 소문자와 '?'로만 구성되어 있다.
• 와일드카드 '?'는 각 검색 키워드의 접두사 혹은 접미사로만 주어진다.

접근 방법

1. 이진 탐색
2. Trie 자료 구조 구현 (미구현)

1. 이진 탐색

• 이진 탐색 메서드인 bisect_left가 문자열들의 배열인 words에서 정상적으로 작동함을 확인
• 검색어 'fro??'에 해당하는 단어들의 첫 인덱스와 마지막 인덱스 찾기
  • bisect_left(words, 'fro??')
    • ord('?') < ord('a')이기 때문에 첫 인덱스를 반환한다.
  • bisect_right(words, 'frozz')
    • '?'를 가장 큰 값인 'z'로 바꾸고 bisect_right하면 조건 해당하는 마지막 인덱스를 반환한다.
• bisect_left, bisect_right
• 각 query마다 길이가 같은 단어들만 후보가 될 수 있기 때문에 길이 별로 저장해두는 것이 좋다.
• 위의 방법은 와일드카드 '?'가 접두사일 때는 작동하지 않는다.
  • 하지만 간단하게 생각하면 접미사일 때 방법에서 모든 단어를 뒤집으면 된다.

2. Trie

Trie는 단어들을 tree 구조에 저장하고 검색할 때 아주 빠른 자료구조이다.
아이디어가 간단해서 Trie 위키를 참고하면 알 수 있을 것이고 이 글에서는 따로 다루지 않을 것이다.

코드

from collections import defaultdict
from bisect import bisect_left, bisect_right


def solution(words, queries):
    answer = []
    d = defaultdict(list) # 구현을 편하게 해준다. 모른다면 찾아보면 좋다.
    r_d = defaultdict(list)
    for word in words:
        d[len(word)].append(word) # 길이 별로 저장
        r_d[len(word)].append(word[::-1]) # 순서를 뒤집은 배열
    for k in d.keys():
        d[k].sort() # 이진 탐색을 위해 sort
        r_d[k].sort() 
        
    for query in queries:
        n = len(query)
        cnt = 0
        e_query = query.replace('?', 'z')
        if query == '?'*n:
            cnt += len(d[n])
        
        elif query[0] == '?':
            query, e_query = query[::-1], e_query[::-1] # 접두사일 때 검색어도 뒤집어주어야 한다.
            l, r = bisect_left(r_d[n], query), bisect_left(r_d[n], e_query)
            cnt += r-l
        else:
            l, r = bisect_left(d[n], query), bisect_left(d[n], e_query)
            cnt += r-l

        answer.append(cnt)
            
    return answer

풀고 난 후

• 검색 키워드에 '?'가 무조건 하나 이상 포함돼 있어 words의 원소와 검색어가 겹치지 않기 때문에 bisect_left만으로도 정답이 나온다.
  • 라고 생각했는데 검색어가 'fro??'일 때 'frozz'인 단어가 있으면 bisect_left를 썼을 때 틀린다.
  • 프로그래머스에서는 정답으로 처리되는데, 테스트케이스 추가가 필요할 것 같다. 은근히 이런 경우가 많다.