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

🔦 문제링크

✍️ 풀이

---

<순서>
1. 접두어 와 접미어 두가지 배열을 만든다.
2. 단어는 단어 길이로 나눌 수 분류할 수 있다.
3. 단어 길이로 분류한 배열을 이진 탐색을 위해 정렬한다.
4. query의 길이와 같은 배열에서 ?를 제외한 문자와 같은 문자열의 갯수를 이진 탐색으로 얻어낸다.

🛠 코드

---

import bisect


def count_by_range(array, left, right):
    left_value = bisect.bisect_left(array, left)
    right_value = bisect.bisect_right(array, right)
    return right_value - left_value


def solution(words, queries):
    answer = []
    arr = dict()
    reverse_arr = dict()
    for word in words:
        length = len(word)
        if not arr.get(length):
            arr[length] = [word]
            reverse_arr[length] = [word[::-1]]
        else:
            arr[length].append(word)
            reverse_arr[length].append(word[::-1])
    for k in arr.keys():
        arr[k].sort()
        reverse_arr[k].sort()
    for query in queries:
        if not len(query) in arr:
            res = 0
        elif query[0] != '?':
            res = count_by_range(arr[len(query)], query.replace('?', 'a'), query.replace('?','z'))
        else:
            res = count_by_range(reverse_arr[len(query)], query[::-1].replace('?','a'), query[::-1].replace('?', 'z'))
        answer.append(res)
    return answer

📝 정리

---

🎈 참고

---

• 이것이 취업을 위한 코딩테스트다 with python
• 나동빈님 답안