bisect 라이브러리 사용

이진 탐색 알고리즘 문제를 풀 때 bisect 라이브러리를 이용하면 쉽게 해결할 수 있는 경우가 있다. 이 라이브러리가 제공하는 기능은 크게 2가지이다.

1. bisect_left(a, x): (정렬된) 리스트 a에 데이터 x를 삽입할 가장 왼쪽 인덱스를 찾는 메서드
2. bisect_right(a, x): (정렬된) 리스트 a에 데이터 x를 삽입할 가장 오른쪽 인덱스를 찾는 메서드

1. 사용법

from bisect import bisect_left, bisect_right

a = [1, 2, 4, 4, 8]
x = 4

print(bisect_left(a, x)) #결과: 2
print(bisect_right(a, x)) #결과: 4

• bisect_left(a, x) 는 2, 4 사이에 들어가면 되므로 2의 인덱스 반환
• bisect_right(a, x)는 4, 8 사이에 들어가면 되므로 4의 인덱스 반환

2. 활용

def count_by_range(a, left_value, right_value):
    left_index = bisect_left(a, left_value)
    right_index = bisect_right(a, right_value)
    return right_index - left_index

arr = [1, 2, 3, 3, 3, 3, 4, 4, 8, 9]
# 값이 4인 원소 개수
print(count_by_range(arr, 4, 4)) # 2
# 값이 [-1, 3] 범위에 있는 데이터 개수 출력
print(count_by_range(arr, -1, 3)) # 6

• bisect_left, bisect_right 메서드를 이용해서 특정 원소의 개수나 left_value <= x <= right_value에 해당하는 데이터의 개수를 반환할 수 있다.