분류

  • 이진 탐색

알고리즘 코드

1
2
3
4
5
6
7
8
9
10
from bisect import bisect_left, bisect_right

def count_by_range(a, left_value, right_value):
    '''
    list a에서 left_value <= x <= right_value인 원소를 찾는 알고리즘
    O(logN)
    '''
    right_index = bisect_right(a, right_value)
    left_index = bisect_left(a, left_value)
    return right_index - left_index

bisect: 정렬을 깨지 않는 선에서 해당 원소를 삽입할 수 있는 위치를 찾는 이진 탐색 함수

관련 문제

2020 KAKAO BLIND RECRUITMENT - 가사 검색

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
from collections import defaultdict
from bisect import bisect_left, bisect_right

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

def solution(words, queries):
    array = defaultdict(list)
    reversed_array = defaultdict(list)
    answer = []
    
    for word in words:
        array[len(word)].append(word)
        reversed_array[len(word)].append(word[::-1])
    
    for k in array.keys():
        array[k].sort()
        reversed_array[k].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

예를들어 fro??를 찾는다면 froaa ~ frozz 사이에 있는 원소의 개수를 찾는다. (정렬이 되어있으므로 가능)

만약 와일드카드가 앞에 존재한다면 문자를 뒤집어서 생각한다.

참고

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