정렬된 배열에서 특정 수의 개수 구하기

1. 문제 설명

---

2. 문제 조건

---

3. 문제 해결 아이디어

• 시간 복잡도를 O(logN)으로 동작하는 알고리즘을 요구하므로 선형 탐색이 아닌 이진 탐색을 수행
  • 데이터가 정렬되어 있기 때문에
• 특정 값이 등장하는 첫 번째 위치와 마지막 위치를 찾아 위치 차이를 계산하여 답을 도출

---

4. 소스 코드

from bisect import bisect_left, bisect_right

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

#데이터의 개수 N, 찾고자 하는 값 x입력받기
n, x = map(int, input().split())
#전체 데이터 입력
array = list(map(int, input().split()))

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

#값이 x인 원소가 존재하지 안흔ㄴ다면
if count == 0:
    print(-1)
#값이 x인 원소가 존재한다면
else:
    print(count)