[이코테] 이진 탐색 - 가사 검색

해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 

 

---

문제설명

하단의 링크를 참조하자.

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

코딩테스트 연습 - 가사 검색

사고과정

• 무엇을 이진탐색하는가?에 대해서, 쿼리로 주어지는 문자열 중 ?로 시작하거나 끝나는 인덱스를 찾는 것인지 했다. 그러나 아니었고 ?의 원소 개수를 이진 탐색으로 세는 것인가 했지만 아니었다..
• 풀이를 보니 이진 탐색으로 원소 개수를 세는 함수를 사용하는 것이었음. 하지만 이 때, 어떤 원소 개수를 세는지에 대해 접근법이 잘못되었음. 필자는 쿼리 하나씩 loop를 돌면서 words들을 모두 탐색하는 것인가 했지만, 풀이에서는 words를 길이별로 2차원 리스트의 인덱스를 word의 길이로 하는 2차원 리스트에 담아나누고 정렬시켰음. 그리고 쿼리 하나하나 돌면서 쿼리의 ?로 되어있는 부분을 a, z로 replace해서 쿼리 기준으로 가장 앞에있는 단어와 끝에있는 단어를 지정해주어서 그 사이에 있는 단어의 개수 찾는 것을 이진 탐색으로 원 소개수를 세는 함수를 활용함. 인상적이었던 점은 ?가 접미사에 나오면 상관없지만 접두사에도 나올 수 있는 경우가 있는데, 이 때는 word를 역정렬(거꾸로)시킨 후 탐색해야 하므로, word의 길이로 하는 2차원 리스트를 2개(순방향, 역방향 정렬)로 각각 운용해서 쿼리가 들어올 때마다 쿼리의 0번 인덱스가 ?이면 역방향 단어들이 기록된 리스트로, ?가 아니면 순방향 단어들이 기록된 리스트로 가도록 설정함..
• 어려웠으나 풀이의 핵심 아이디어만 보고 스스로 구현하기 위해서 노력함.. 거의 구현했지만 시간 초과에서 판정이 나왔는데, 2차원 리스트 2개안에 있는 각각의 단어들을 한 번 정렬시켜주어야 하는데, 처음엔 쿼리가 도는 loop 마다 sorted를 설정해놓았음.. 이렇게 하지말고 쿼리 받기 전에 아예 선형적으로 모든 리스트 원소들에 대해 정렬시켜주면 시간 초과 판정을 받지 않음

풀이(스스로 못 푼 풀이)

from bisect import bisect_left, bisect_right

def count_by_range(array, left_val, right_val):
    left_idx = bisect_left(array, left_val)
    right_idx = bisect_right(array, right_val)
    return right_idx - left_idx

def solution(words, queries):
    answer = [0] * len(queries)
    asc_words = [[] for _ in range(100001)]
    desc_words = [[] for _ in range(100001)]
    # 단어 길이를 인덱스로하는 2차원 리스트에 단어 길이별로 담기
    for word in words:
        asc_words[len(word)].append(word)
        desc_words[len(word)].append(word[::-1])

    # 단어 길이별로 단어들 정렬
    for i in range(100001):
        asc_words[i].sort()
        desc_words[i].sort()

    # 쿼리하나씩 받아서 처리
    for i in range(len(queries)):
        q = queries[i]
        if q[0] != '?':
            answer[i] = count_by_range(asc_words[len(q)], q.replace('?', 'a'),
                                       q.replace('?', 'z'))
        else:
            q = q[::-1]
            answer[i] = count_by_range(desc_words[len(q)], q.replace('?', 'a'),
                                       q.replace('?', 'z'))

    return answer