[이진탐색] Q27 정렬된 배열에서 특정 수의 개수 구하기

난이도: 2 / 풀이 시간: 30분

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

---

방법 1

• binarySearch 직접 구현 + 이진탐색의 조건을 수정
• 좌측값 탐색함수, 우측값 탐색함수 별도로 분리
• 우측값 - 좌측값 + 1 반환

import sys
input = sys.stdin.readline

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

def binarySearchLeft(array, target, start, end):
    while start <= end:
        mid = (start+end) // 2
        if array[mid] == target and (mid == 0 or array[mid-1] < target):
            return mid
        elif target <= array[mid]:
            end = mid - 1
        else:
            start = mid + 1
    return -1

def binarySearchRight(array, target, start, end):
    while start <= end:
        mid = (start+end) // 2
        if array[mid] == target and (mid == len(array)-1 or array[mid+1] > target):
            return mid
        elif target < array[mid]:
            end = mid - 1
        else:
            start = mid + 1
    return -1

leftIndex = binarySearchLeft(nums, x, 0, n-1)
rightIndex = binarySearchRight(nums, x, 0, n-1)
if leftIndex == -1 or rightIndex == -1:
    print(-1)
else:
    print(rightIndex - leftIndex + 1)

방법 2

• bisect 라이브러리 사용 from bisect import bisect_left, bisect_right
• count_by_range 함수 구현
• count = count_by_range(nums, x, x) 값을 통해 구현

import sys
from bisect import bisect_left, bisect_right
input = sys.stdin.readline

def count_by_range(array, leftValue, rightValue):
    leftIndex = bisect_left(array, leftValue)
    rightNextIndex = bisect_right(array, rightValue)
    return rightNextIndex - leftIndex

n, x = map(int, input().split())
nums = list(map(int, input().split()))
count = count_by_range(nums, x, x)

if count == 0:
    print(-1)
else:
    print(count)