[python] bisect / 이진 탐색 내장함수

import bisect

 

두가지 종류로 분류 가능

• 주어진 리스트 list, 값 x가 있을 때, x가 들어갈 인덱스를 구하는 함수
• 값 x를 이진탐색으로 넣는 함수

 

bisect.bisect_left(list, x) : list에서 x가 들어가야할 인덱스 값을 구한다

bisect.bisec_right(list, x) : list에서 x가 들어가야할 인덱스 값을 구하지만, 동일한 값이 있을 경우 동일한 값의 오른쪽 인덱스 값을 구한다

 bisect.insort(list, x) : binary search로 x 값을 list에 넣는다

 

 

EX 문제

https://www.hackerrank.com/challenges/fraudulent-activity-notifications/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=sorting

Fraudulent Activity Notifications | HackerRank

 

import bisect

def activityNotifications(expenditure, d):
    result = 0
    arr = sorted(expenditure[:d])
    
    for i in range(len(expenditure)-d):
        if d % 2 == 1:
            median = arr[d//2]
        else:
            median = (arr[d//2-1] + arr[d//2]) / 2
        if 2 * median <= expenditure[i+d]:
            result += 1
            
        del_index = bisect.bisect_left(arr, expenditure[i])
        arr.pop(del_index)
        bisect.insort(arr, expenditure[i+d])

    return result

median값을 구할때마다 sort하면 timeout에 걸린다
처음 d개의 배열을 정렬해놓고
기존배열에 0번 인덱스값 삭제 - 이진탐색으로 삽입을 반복한다