가사 검색

📌문제

https://school.programmers.co.kr/learn/courses/30/lessons/60060

프로그래머스

 

📌풀이

각 단어를 길이에 따라 나눈 후 각 리스트를 정렬

이진 탐색을 이용하여 쿼리에 해당하는 특정 단어의 개수를 계산

 

📌코드

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

 

📌참고

https://g.co/kgs/eyd5SSd

이것이 취업을 위한 코딩 테스트다 with 파이썬