[이.취.코] Chap 15. 이진탐색 - Q27. 정렬된 배열에서 특정 수의 개수 구하기

@mildsalmon·2021-10-09 19:30

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

난이도
- 중
풀이 시간
- 30분
시간 제한
- 1초
메모리 제한
- 128 MB
출처
- Zoho 인터뷰

A. 📜 문제

N개의 원소를 포함하고 있는 수열이 오름차순으로 정렬되어 있다. 이때 이 수열에서 x가 등장하는 횟수를 계산하라.

단, 이 문제는 시간 복잡도 O(logN)으로 알고리즘을 설계하지 않으면 시간 초과 판정을 받는다.

a. 예를 들면.

수열 {1, 1, 2 ,2 ,2 ,2, 3}이 있을 때 x=2라면, 현재 수열에서 값이 2인 원소가 4개이므로 4를 출력한다.

b. 입력 조건

첫째 줄에 N과 x가 정수 형태로 공백으로 구분되어 입력된다.
- 1 <= N <= 1,000,000
- -1e9 <= x <= 1e9
둘째 줄에 N개의 원소가 정수 형태로 공백으로 구분되어 입력된다
- -1e9 <= 각 원소의 값 <= 1e9

c. 출력 조건

수열의 원소 중에서 값이 x인 원소의 개수를 출력한다. 단 값이 x인 원소가 하나도 없다면 -1일 출력한다.

d. 테스트 케이스

입력 예시


7 2
1 1 2 2 2 2 3


7 4
1 1 2 2 2 2 3

출력 예시
```
4
```
```
-1
```

B. 💡 내 답안

a. 😊 1차 시도 (성공)


def bi_sec(start, end, target, array):
    while start <= end:
        mid = (start + end) // 2

        if array[mid] == target:
            return mid

        if array[mid] > target:
            end = mid -1
        elif array[mid] < target:
            start = mid + 1
    return 0

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

start = 0
end = n-1

pre = bi_sec(start, end, x-1, array)
post = bi_sec(start, end, x+1, array)

answer = (post - 1) - (pre + 1) + 1

if post - pre > 0:
    print(answer)
else:
    print(-1)