정렬된 배열에서 특정 수의 개수 구하기(이진 탐색 라이브러리 bisect)

 

해결법

이 문제는 원하는 숫자 x의 가장 첫번째 위치와 마지막 위치를 구해서 빼면 되는 문제이다.

 

-bisect 라이브러리

from bisect import bisect_left, bisect_right

bisect_right(ary, x) 
bisect_left(ary, x)

ary는 집합, x는 원하는 값 이렇게 작성하면 된다.

예를 들어 bisect_right는 정렬된 순서를 유지하면서 리스트 a에 데이터 x를 삽입할 가장 오른쪽 인덱스를 찾아준다. 시작 복잡도는 O(logN)이다.

 

교재 코드

from bisect import bisect_left, bisect_right

n, x = map(int, input().split())
ary = list(map(int, input().split()))

answer = bisect_right(ary, x) - bisect_left(ary, x)

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

처음에 라이브러리도 몰랐고 문제 풀이법도 생각하지 못했다ㅠㅠ