[Python] bisect 활용해 범위 탐색하기

Peter·2021년 3월 30일
0
list = [1, 1, 2, 2, 2, 2, 3]

위와 같은 리스트가 있을 때
2의 개수를 세고 싶다면

count = list.count(2)
print(count)

4

위 코드 처럼 count 메소드를 사용하면 된다
시간복잡도는 O(n)이다
리스트의 길이가 억단위로 넘어가게 되면 시간복잡도 측면에서 불리할 수 있다

파이썬에서 제공하는 bisect를 사용해보자

from bisect import bisect_left, bisect_right

list = [1, 1, 2, 2, 2, 2, 3]

right = bisect_right(list, 2)
left = bisect_left(list, 2)

print(left, right)

2 6

bisect_right, bisect_left 를 사용해준다면
첫번째 인자 list 에서
두번째 인자가 각각 오른쪽 왼쪽에 처음으로 나오는 위치를
이진탐색을 통해 탐색한뒤 인덱스를 반환해준다
시간복잡도는 각각 O(logn)이 걸리는데
억단위의 많은 엘리먼츠를 가진 리스트 안에서 유리한 탐색을 할 수 있다.

bisect_left(리스트, 찾을녀석, 범위처음, 범위끝)

위 형태로 탐색 범위도 설정 가능하다

외에도 bisect는 insort 라는 함수를 가지고 있는데
정렬된 리스트에 엘리먼트를 정렬에 맞게 추가하고 싶을때 사용가능하다

from bisect import insort

list = [1, 1, 2, 2, 2, 2, 3]

insort(list, 2)

print(list)

[1, 1, 2, 2, 2, 2, 2, 3]

위처럼 정렬이 틀어지지 않는다.

profile
컴퓨터가 좋아

0개의 댓글