🤢 문제
N개의 원소를 포함하고 있는 수열이 오름차순으로 정렬되어 있습니다. 이때 이 수열에서 x가 등장하는 횟수를 계산하세요. 예를 들어 수열 [1, 1, 2, 2, 2, 2, 3]이 있을 때 x=2라면, 현재 수열에서 값이 2인 원소가 4개이므로 4를 출력합니다.
단, 이 문제는 시간 복잡도 O(logN)으로 알고리즘을 설계하지 않으면 '시간 초과' 판정을 받습니다.
입력 조건
- 첫째 줄에 N과 x가 정수 형태로 공백으로 구분되어 입력됩니다.
(1 <= N <= 1,000,000), (-10^9 <= x <= 10^9) - 둘째 줄에 N개의 원소가 정수 형태로 공백으로 구분되어 입력됩니다.
(-10^9 <= 각 원소의 값 <= 10^9)
출력 조건
- 수열의 원소 중에서 값이 x인 원소의 개수를 출력합니다. 단, 값이 x인 원소가 하나도 없다면 -1을 출력합니다.
입력 예시1
7 2
1 1 2 2 2 2 3출력 예시 1
4입력 예시 2
7 4
1 1 2 2 2 2 3출력 예시 2
-1🤔 내 풀이
n,x = map(int, input().split())
array = list(map(int, input().split()))
def binary_search(start, end, target, sum):
while start<=end:
mid = (start + end) // 2
if mid == 7:
return sum
if array[mid] == target:
sum += 1
del array[mid]
return sum
elif array[mid] < target:
start = mid + 1
else:
end = mid - 1
return sum
sum=0
for i in array:
sum = binary_search(0, n, x, sum)
if sum == 0:
print(-1)
else:
print(sum)
:]