출처 - 이것이 취업을 위한 코딩테스트다 with 파이썬
정렬된 배열에서 특정 수의 개수 구하기
📌 문제
N개의 원소를 포함하고 있는 수열이 오름차순으로 정렬되어 있다. 이때 이 수열에서 x가 등장하는 횟수를 계산하세요. 예를 들어 수열 [1, 1, 2, 2, 2 ,2 ,3]이 있을 때 x = 2라면, 현재 수열에서 값이 2인 원소가 4개이므로 4를 출력한다.
단, 이 문제는 시간 복잡도 O(logN) 으로 알고리즘을 설계하지 않으면 '시간 초과' 판정을 받는다.
📋 코드
from bisect import bisect_left, bisect_right
N, x = map(int, input().split())
arr = list(map(int, input().split()))
left, right = bisect_left(arr, x), bisect_right(arr, x)
print(-1 if right - left == 0 else right - left)💡 한마디
bisect 라이브러리를 이용했다. bisect_left(arr, x) 는 정렬된 arr 리스트에서 x라는 왼쪽에서부터 몇 번째 인덱스에 들어갈 수 있는지를 알려준다. bisect_right(arr, x) 는 x를 삽입할 가장 오른쪽 인덱스를 알려준다.
