Python - bisect 예제

[ bisect 모듈 ]

bisect 모듈은 이진 탐색을 쉽게 쓸 수 있게 해주는 파이썬 표준 라이브러리

"정렬된 리스트"에 값을 효율적으로 삽입하거나 위치를 찾을 때 유용

 

 

[ 사용 함수 ]

함수	의미	반환값
bisect_left(a, x)	좌측 삽입 위치 탐색	x를 a에 넣을 때 왼쪽 인덱스
bisect_right(a, x)	우측 삽입 위치 탐색	x를 a에 넣을 때 오른쪽 인덱스
insort_left(a, x)	bisect_left 위치에 삽입	리스트 a가 정렬된 상태 유지
insort_right(a, x)	bisect_right 위치에 삽입	동일

 

 

[ 예제 ]

정렬 리스트에 중복을 허용하며 요소 삽입

import bisect

scores = [15, 22, 22, 30]
bisect.insort(scores, 22)      # insort == insort_right
print(scores)                  # [15, 22, 22, 22, 30]

 

리스트에 같은 값이 몇개 있는지 확인

a = [1, 2, 2, 2, 3, 4, 5]
lo = bisect.bisect_left(a, 2)   # 1
hi = bisect.bisect_right(a, 2)  # 4
count = hi - lo                 # 3

 

실시간 랭킹 유지

from bisect import insort_right

leaderboard = []          # (score, user) 튜플의 내림차순 리스트
def add_score(score, user):
    # 점수가 큰 순으로 정렬하기 위해 음수 key 사용, 튜플(-score, user)
    insort_right(leaderboard, (-score, user))

add_score(300, "Alice")
add_score(270, "Bob")
add_score(285, "Carol")

print(leaderboard[:3])    

>>> 출력
[(-300, 'Alice'), (-285, 'Carol'), (-270, 'Bob')]

 

 

[ 문제 ]

정수 배열 nums와 정수 n이 주어질 때, 증가 부분 수열(subsequence) 구하기

예제 1

nums = [2, 1, 5, 0, 4, 6]
n    = 3

가능한 증가 부분 수열 예: [2, 5, 6], [1, 4, 6], [0, 4, 6] 등이 있으므로
→ True

예제 2

nums = [5, 4, 3, 2, 1]
n    = 2

모든 값이 내림차순이므로 길이 2인 증가 부분 수열도 만들 수 없음
→ False

 

이 문제를 O(N log N) 시간에 해결하는 표준 기법(그리디+이진 탐색)을 구현한 예시

import bisect

def increasingSubsequence(nums, n):
    tail = []  # 각 길이별 수열의 최소 마지막 값 저장

    for num in nums:
        idx = bisect.bisect_left(tail, num)  # 현재 num이 들어갈 자리
        if idx == len(tail):
            tail.append(num)  # 새로운 길이의 수열이 생김
        else:
            tail[idx] = num  # 기존 길이 수열의 최소 마지막 값 갱신

        if len(tail) >= n:
            return True  # n중 수열 발견

    return False