bisect 모듈

안녕하세요. 오늘은 코딩테스트에서 종종 이용하게 되는 bisect 모듈에 대해서 알아보겠습니다.

bisect 모듈이란

import bisect

bisect 모듈이란 정렬된 배열에서 이진 탐색을 쉽게 구현할 수 있도록 도와주는 모듈입니다. 이진 탐색을 코드로 직접 구현하는 방법도 가능하지만, 정렬된 배열에서 크기를 비교하는 간단한 문제라면 bisect 모듈을 이용하여 더 쉽게 구현이 가능합니다. 이진 탐색을 구현한 모듈이기 때문에 시간복잡도는 O(logN)입니다.

주로 사용되는 함수는 다음과 같습니다.

bisect_left

bisect_left(array, item):정렬된 배열 array에서 item을 삽입할 수 있는 가장 왼쪽 인덱스를 반환합니다.

from bisect import bisect_left


nums = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
print(bisect_left(nums, 5)) # 출력 결과: 5

nums = [4, 5, 5, 5, 5, 5, 5, 5, 5, 6]
print(bisect_left(nums, 5)) # 출력 결과: 1

첫 번째 nums 배열에서 5가 들어갈 가장 왼쪽 위치는 4와 5 사이겠죠?
그렇다면 삽입될 위치의 인덱스는 5가 됩니다.

두 번째 nums 배열에서 5가 들어갈 가장 왼쪽 위치 역시 4와 맨 처음 나오는 5 사이입니다.
그렇다면 삽입될 위치의 인덱스는 1이 되겠죠.

bisect_right

bisect_right(array, item): 정렬된 배열 array에 item을 삽입할 수 있는 가장 오른쪽 인덱스를 반환합니다.

from bisect import bisect_right

nums = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
print(bisect_right(nums, 5)) # 6

nums = [4, 5, 5, 5, 5, 5, 5, 5, 5, 6]
print(bisect_right(nums, 5)) # 9

첫 번째 nums 배열에서 5가 들어갈 가장 오른쪽 위치는 5와 6 사이입니다.
따라서 삽입될 위치의 인덱스는 6이 됩니다.

두 번째 nums 배열에서 5가 들어갈 가장 오른쪽 위치는 맨 마지막 5와 6 사이입니다.
그렇다면 삽입될 위치의 인덱스는 9가 되겠죠.

활용 - 특정 범위에 속하는 원소 개수 구하기

bisect_left와 bisect_right을 이용하면 정렬된 배열에서 특정 범위에 속하는 원소의 개수를 쉽게 구할 수 있습니다.

def count(nums, left_limit, right_limit):
    left_idx = bisect_left(nums, left_limit)
    right_idx = bisect_right(nums, right_limit)
    return right_idx - left_idx

# 사용
scores = [ ... ] # 정렬된 배열
count(scores, 80, 90)

위 코드의 count 함수는 주어진 범위의 왼쪽 끝 값과 오른쪽 끝 값을 인자로 받습니다. 그리고 bisect_left와 bisect_right을 이용하여 배열에서 이 두 값의 인덱스를 각각 구하고 그 차이를 반환합니다. count 함수가 인자로 받는 배열은 정렬된 배열이기 때문에 양쪽 범위 끝 값의 인덱스 차이가 해당 배열 안에서 범위 내에 속하는 값들의 개수가 되는 것이죠.

배열을 그대로 순회한다면 O(N)의 시간이 필요하겠지만, 이진 탐색을 이용한다면 O(logN)의 시간복잡도로 해결이 가능합니다!
(물론 배열이 정렬되어 있다는 조건이 필요합니다. 그렇지 않다면 정렬하는데 보통 O(NlogN)의 시간이 소모되기 때문이죠.)

이렇게 bisect 모듈에 대해서 알아보았습니다. 감사합니다.