이코테_정렬된 배열에서 특정 수의 개수 구하기

문제

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을 출력합니다.

풀이

처음엔 그냥 찾아야 하는 숫자가 가장 먼저 나오는 인덱스, 가장 나중에 나오는 인덱스를 구한 뒤 두 값을 빼기만 하면 되는 간단한 문제로 생각하고 투 포인터를 이용하여 문제를 풀려 하였다. 하지만 시간 측정 때 생각보다 긴 시간이 소요되었고 찾아본 결과 투 포인터는 최악의 경우에는 O(N)의 시간 복잡도를 가진다는 것을 알게되었다.
결국 O(logN)의 시간복잡도를 항상 보장하는 이진탐색으로 문제를 다시 풀었다. 풀이에 생각보다 많은 시간이 소요되어 솔루션을 참고하여 문제를 풀었다.

풀이 1

코드

import sys
import time

start_time = time.time()
input = sys.stdin.readline

n, m = map(int,input().split())

num_list = list(map(int,input().rstrip().split()))

def first_idx(arr, start, end, target):
    if start > end:
        return None
    mid = (start + end) // 2
    
    if (mid == 0 or target > arr[mid - 1]) and arr[mid] == target:
        return mid
    elif arr[mid] >= target:
        return first_idx(arr,start, mid -1, target)
    else:
        return first_idx(arr,mid + 1, end, target)
             
             
def last_idx(arr, start, end, target):
    if start > end:
        return None
    mid = (start + end) // 2
    
    if (mid == n-1 or target < arr[mid + 1]) and arr[mid] == target:
        return mid
    elif arr[mid] > target:
        return last_idx(arr,start, mid -1, target)
    else:
        return last_idx(arr,mid + 1, end, target)
    
first = first_idx(num_list, 0, n-1, m)
last = last_idx(num_list,0, n-1, m)
if first == None:
    first = 0
result = last - first + 1

if result == 0:
    print(-1)
else:
    print(result)
    
end_time = time.time()
print(f"걸린 시간 : {end_time - start_time}")

풀이 2

이 풀이는 파이썬의 이진탐색 라이브러리리인 bisect를 활용한 코드이다.

from bisect import bisect_left, bisect_right

def count_by_range(arr, left_value, right_value):
    right_idx = bisect_right(arr, right_value)
    left_idx = bisect_left(arr, left_value)
    return right_idx - left_idx

n, m = map(int,input().split())
arr = list(map(int,input().split()))


cnt = count_by_range(arr, m, m)

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