[Python] 이코테 Chapter 15 정렬된 배열에서 특정 수의 개수 구하기

문제

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

 

풀이

import sys
from copy import deepcopy 
from collections import deque
import bisect
ip = sys.stdin.readline

n,x = map(int,ip().split())

arr = list(map(int,ip().split()))
res = bisect.bisect_right(arr,x)-bisect.bisect_left(arr,x)
if res == 0 :
    print(-1)
else :
    print(res)

주어진 배열에서 x의 개수를 찾는 문제이다.

배열에서 x의 처음 등장 위치(lower_bound)와 x보다 큰수의 처음 등장 위치(upper_bound)를 구해준 후 둘을 빼주면 x의 개수가 나온다.

 

파이썬에서 c++의 lower_bound와 upper_bound 기능을 구현하기 위해 bisect 모듈을 사용하였다.