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

이 문제는 O(logN)으로 알고리즘을 설계하지 않으면 시간 초과가 나오는 문제이다.

따라서 일반적인 for문을 활용하여 리스트를 탐색하면 시간 초과가 난다!

그렇기에 O(logN)의 시간 복잡도를 가지는 이진 탐색을 활용해야 한다.

 

직접 이진 탐색을 구현할 수도 있지만 파이썬의 라이브러리와 친숙해지기 위해 bisect 라이브러리를 사용했다.

bisect는 특정 숫자 사이에 있는 원소의 개수를 구할 때 유용하게 사용된다.

여기서 주의할 점은 array가 오름차순으로 sorting되어 있어야 한다는 점이다!

 

해당 문제의 경우 이미 오름차순으로 정렬된 수열이 input값으로 들어온다.

• bisect_right(array, N)
  • 배열에서 N이 마지막으로 등장하는 인덱스+1을 리턴함
• bisect_left(array, N)
  • 배열에서 N이 처음으로 등장하는 인덱스를 리턴함

 

🖥 예시

# input
N, X = 7, 2
list = 1 1 2 2 2 2 3

bisect_right(list, 2) => return 6
bisect_left(list, 2) => return 2

 

🖥  문제 풀이 코드

import sys
from bisect import bisect_right, bisect_left

N, X = map(int, sys.stdin.readline().split())
nums = list(map(int, sys.stdin.readline().split()))

def numCount():
  r_index = bisect_right(nums, X)
  l_index = bisect_left(nums, X)
  result = r_index - l_index
  if result == 0: result = -1
  return result

print(numCount())