Bisect

• 정렬된 배열에서 특정 원소 찾을때

  → O(logN)에 동작

• bisect_left(a, x)

  : 정렬된 순서를 유지하면서 리스트 a에 데이터 x 삽입할 가장 왼쪽 인덱스 찾기

• bisect_right(a, x)

  : 정렬된 순서를 유지하면서 리스트 a에 데이터 x 삽입할 가장 오른쪽 인덱스 찾기

  → 값이 특정 범위에 속하는 원소의 개수

from bisect import bisect_right, bisect_left

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

print(bisect_left(a,x))
print(bisect_right(a,x))

• count_by_range(a, left_value, right_value)

  : 정렬된 리스트 a 에서 left_value≤x≤ right_value인 x개수를 O(logN)으로 찾기

from bisect import bisect_right, bisect_left

def count_by_range(a, left_value, right_value):
    rindex = bisect_right(a, right_value)
    lindex = bisect_left(a, left_value)
    return rindex-lindex

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

print(count_by_range(a,4,4))

문제설명

N개의 원소를 포함하는 수열이 오름차순 정렬되어있을때, 수열 x가 등장하는 횟수는? 단, O(logN)으로 설계, 원소가 하나도 없으면 -1 출력

IN
N, x

OUT
x가 등장하는 횟수

코드

#bisect 이용

from bisect import bisect_left, bisect_right

#값이 [left_value, right_value]인 데이터의 개수를 반환
def count_by_range(array, left_value, right_value):
    right_index = bisect_right(array, right_value)
    left_index = bisect_left(array, left_value)
    return right_index - left_index

N, x = map(int, input().split())
nums = list(map(int, input().split()))

#값이 [x,x]범위에 있는 데이터의 개수 계산
count = count_by_range(array, x, x)

if count == 0: 
    print(-1)
else:
    print(count)