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)
'CodingTest > 이진 탐색' 카테고리의 다른 글
떡볶이 떡 만들기 (0) | 2022.07.12 |
---|---|
값이 특정 범위에 속하는 데이터 개수 구하기 (0) | 2022.07.12 |
이진 탐색 알고리즘 이론 (0) | 2022.07.12 |