가사 검색

 

유형 분석 및 구현

이 문제는 일단 이진탐색으로 풀되, 문자열을 뒤집는 방법이나 bisect활용을 다양하게 할 줄 아는가에 대한 여부를 파악해야하는 문제인 듯 하다.

 

또한 효율성 체크 또한 중요하다.

- 항상 답안 제출시 print 남용된것 없나 확인

- 각 행을 정렬할건지 전체 리스트를 정렬할건지 확인하자

- 문제에 n(배열의 크기)가 입력되지 않는다면 max값으로 설정하자.

 

 

코드

from bisect import bisect_left, bisect_right


# 찾고자하는 문자열의 시작인덱스와 마지막인덱스를 구할 수 있다.
# 또한 이 문제 같은 경우는 left_value와 right_value를 달리하여
# left_value < 데이터 < right_value , 즉, 해당 범위 안에 있는 값을 찾을 수 있다.

def count_by_sort(array, left_value, right_value):
    left_index = bisect_left(array, left_value)
    right_index = bisect_right(array, right_value)
    return right_index - left_index


# 그대로 사용할 문자열과 문자열을 역처리한 것을 담을 초기리스트
w_correct = [[] for _ in range(10001)]
w_reverse = [[] for _ in range(10001)]



def solution(words, queries):
    
    # 글자 길이마다 정리
    for i in range(len(words)):
        w_correct[len(words[i])].append(words[i])
        w_reverse[len(words[i])].append(words[i][::-1])

	# 정리한 것 삽입
    for i in range(10001):
        w_correct[i].sort()
        w_reverse[i].sort()
    
    # 최종 결과
    final_result = []
    
    # 쿼리마다 글자가 해당되는게 있는지 확인
    for query in queries:
        q_length = len(query)
        if query[0] != "?":
            result = count_by_sort(w_correct[q_length], query.replace('?', 'a'), query.replace('?', 'z'))
        else:
            result = count_by_sort(w_reverse[q_length], query[::-1].replace('?', 'a'), query[::-1].replace('?', 'z'))
        final_result.append(result)
        
    return final_result