[프로그래머스]Lv.4 가사 검색(Python)

문제

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

풀이

굉장히 복잡한 문제였다.

문제의 설명대로 구현하면 예제 케이스는 통과할 수 있다.

하지만, 각 데이터의 범위로 인해서 시간초과가 발생할 수 있다.

쿼리마다 글자수가 동일한지 여부를 체크한다던가, 접미사에 붙은 와일드 카드를 비교한다던가, 조건에 맞는 단어마다 1씩 카운팅 한다던가...

이런식으로 코드를 작성하면 O(n^2)의 시간복잡도가 등장하므로 시간초과가 발생한다.

 

1. 글자수별로 분류한다.

 

각 쿼리마다 단어들의 글자수가 맞는지 체크하지 말고, 단어의 길이마다 단어를 분류하면 쿼리마다 길이가 맞는 단어만 비교할 수 있다.

 

2. 접미사를 전부 접두사처럼

 

접미사도 접두사처럼 검증해서 로직을 단순화하고, 직관적으로 선형 시간복잡도를 갖게 할 것이다.

 

3. 와일드카드에 해당하는 범위를 구해서 시작과 끝 인덱스를 뺀다.

 

와일드 카드는 a부터 z까지 등장할 수 있으니 차라리 정렬시켜서 시작과 끝 인덱스를 구해서 한번에 처리한다.

정렬했으므로 빠른 탐색이 가능하다.

제출 코드

from bisect import bisect_right, bisect_left


def solution(words, queries):
    
    def count(array, left_value, right_value):
        # 시작점 인덱스를 구한다.
        left_index = bisect_left(array, left_value)
        # 끝점 인덱스를 구한다.
        right_index = bisect_right(array, right_value)
        # 해당 와일드 카드에 대한 단어들의 개수
        return right_index - left_index
    
    array = [[] for _ in range(10_001)]
    reversed_array = [[] for _ in range(10_001)]
    # 단어 길이별로 단어들 분류
    # ??abc -> fdabc, fdabcd len() => O(n), array[len(wild_word)]
    # fd???
    # O(n) => O(100_000)
    for word in words:
        array[len(word)].append(word)
        reversed_array[len(word)].append(word[::-1])
    
    for i in range(10_001):
        array[i].sort() # ??abc , aaabc -> zzabc 범위 시작 인덱스와 끝인덱스만 찾아서 빼자 => 그 단어의 갯수
        reversed_array[i].sort()
    
    answer = []
    for query in queries:
        if query[0] != '?':
            # 접미사 검색처리
            left_value = query.replace('?', 'a')
            right_value = query.replace('?', 'z')
            
            result = count(
                array[len(query)], left_value, right_value
            )
        else:
            # 접두사 검색처리
            reversed_query = query[::-1]
            
            left_value = reversed_query.replace('?', 'a')
            right_value = reversed_query.replace('?', 'z')
            
            result = count(
                reversed_array[len(query)], left_value, right_value
            )
        answer.append(result)
    return answer

 

참고로 처음에는 인덱스 구하는 함수를 직접 구현했었는데, 알고보니 Python은 bisect 라이브러리가 있어서 위처럼 작성했다. 더 간결하게 표현할 수 있고, 효율성도 높아졌다.