[ProblemSolving] *정렬된 특정수의 배수구하기(이진탐색)

채점 불가능한 문제입니다.

문제 설명

N개의 원소를 포함하고 있는 수열이 오름차순으로 정렬되어 있습니다. 이때 이 수열에서 x가 등장하는 횟수를 계산하세요.
단, 이 문제의 시간 복잡도 O(logN)으로 알고리즘을 설계하지 않으면 '시간 초과' 판정을 받습니다.

입력

첫째 줄에 N과 x가 정수 형태로 공백으로 구분되어 입력됩니다.
(1 ≤ N ≤ 1,000,000), (-10⁹ ≤ x ≤ 10⁹)
둘째 줄에 N개의 원소가 정수 형태로 공백으로 구분되어 입력됩니다.
(-10⁹ ≤ 각 원소의 값 ≤ 10⁹)

출력

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

예제 입력1

7 2
1 1 2 2 2 2 3

예제 출력1

4

풀이

시간복잡도 O(logN)으로 설계해야하므로 선형탐색을 이용해 해결할 수 없다.
정렬된 원소를 입력받으므로, 이진탐색을 이용하여 접근한다.
X가 처음 등장하는 인덱스와 마지막으로 등장하는 인덱스를 각각 계산하여 그 차이를 계산하여 문제를 해결할 수 있다.
따라서 이진탐색 함수를 2개 만든다..

코드

• 이진 탐색 함수 2개 활용

# 정렬된 수열에서 x의 개수 세기
def count_by_value(array, x):
    n = len(array)
    a = first(array, x, 0, n-1)
    if a == None:
        return 0
    b = last(array, x, 0, n-1)
    return b-a+1

def first(array, target, start, end):
    if start > end:
        return None
    mid = (start + end)//2
    # (array 크기가 2라면 mid가 첫번째 원소인 경우) 가장 왼쪽에 있는 경우
    if (mid==0 or target > array[mid-1]) and array[mid] == target:
        return mid
    elif array[mid] >= target:
        return first(array, target, start, end-1)
    else:
        return first(array, target, mid+1, end)
    
def last(array, target, start, end):
    if start > end:
        return None
    mid = (start + end) //2
    
    if (mid== n-1 or target < array[mid+1]) and array[mid] == target:
        return mid
    elif array[mid] > target:
        return last(array, target, start, end-1)
    else:
        return last(array, target, mid+1, end)
        

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

count = count_by_value(array, x)

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

• 이진탐색 라이브러리 활용

# 이진 탐색 라이브러리 bisect 활용
from bisect import bisect_left, bisect_right

def count_by_range(array, left, right):
    right_index = bisect_right(array, right)
    left_index = bisect_left(array, left)
    return right_index - left_index

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

#  [x, x] 범위에 있는 데이터를 계산하겠다
count = count_by_range(array, x, x)
if count == 0:
    print(-1)
else:
    print(count)