[Python] 가사 검색

문제

프로그래머스

입력 예시

words = ["frodo", "front", "frost", "frozen", "frame", "kakao"]
queries = ["fro??", "????o", "fr???", "fro???", "pro?"]

출력 예시

[3, 2, 4, 1, 0]

문제 풀이

• 접두사인 경우 편하게 탐색하기 위해 쿼리 뒤집어서 탐색
• 각 단어들을 단어길이번째 인덱스에 저장 (단어 길이별로 따로 저장)
• 접두사와 접미사 따로 탐색하기 위해 단어들을 뒤집은 상태도 저장
• 이진탐색 진행하기 위해 각 배열들 정렬
• 접두사와 접미사인 경우 따로 탐색 진행
  • ?를 a와 z로 치환한 후, bisect_left와 bisect_right를 사용하여 a와 z사이의 단어 개수를 구하면 와일드카드 문자가 아닌 다른 문자들이 같은지 확인할 수 있다
  • 같은문자 개수 반환하는 count_by_range 함수 따로 구현
• 탐색 마친 후 같은 문자 개수 추가하기
• 같은 문자 개수들 모두 출력

코드

from bisect import bisect_left,bisect_right
# words = ["frodo", "front", "frost", "frozen", "frame", "kakao"]
# queries = ["fro??", "????o", "fr???", "fro???", "pro?"]
array = [[] for _ in range(10001)]
reversed_array = [[] for _ in range(10001)]

# 값이 left_value, right_value인 값 반환하는 함수
def count_by_range(a, left_value, right_value):
    left_index = bisect_left(a,left_value)
    right_index = bisect_right(a, right_value)
    return right_index - left_index

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

# print(solution(words,queries))