책 367p

문제

• 시간제한
  • 1초
• 입력
  • 첫째줄에 N과 x . (1<=N<=1,000,000) ($-10^9<=x<=10^9$)
  • 둘째줄에 N개의 원소 ($-10^9<=각 원소의 값<=10^9$)
• 출력
  • 수열의 원소 중에서 값이 x인 원소의 갯수를 출력. 하나도 없다면 -1

N개의 원소를 포함하는 수열이 오름차순으로 정렬되어있다.
이 수열에서 x가 등장하는 횟수를 계산하시오.
이 문제는 O(logN)으로 설계하지 않으면 시간초과.

풀이

처음 든 생각

하하 정렬된 상태에서 빠르게 찾으세요 하하 감사합니다 이진탐색 쓰겠습니다

풀이 아이디어

정렬되어있는 N개 원소에서 target을 찾는 이진탐색의 시간복잡도는 O(logN).
x가 존재한다면 연속 나열 되어 있을 것이므로, x가 첨 등장하고 마지막으로 등장하는 인덱스를 각각 계산하여 차이를 계산하자.

기억하자!

• x가 첨 등장하는 인덱스를 계산하는 함수 한개
• x가 마지막으로 등장하는 인덱스를 계산하는 함수 한개
  이렇게 두개를 마련하여 계산하는것은
  이진탐색요구 고난이도 문제에서 자주 사용하는 테크닉이다.

코드

# 정렬된 수열에서 값이 x인 원소의 갯수를 세는 메소드
def count_by_value(array, x) :
	# 데이터의 갯수
	n = len(array)

	# X가 처음 등장한 인덱스 계산
	a = first(array, x, 0, n-1)

	# 수열에 x가 존재하지 않는 경우
	if a ==  None :
		return 0 #값이 x인 원소의 갯수는 0개이므로 0 반환

	# x가 마지막으로 등장한 인덱스 계산
	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
	# 해당 값을 가지는 원소 중에서 가장 왼쪽에 있는 경우에만 인덱스 반환
	if (mid == 0 or target > array[mid-1]) and array[mid] == target :
		return mid
	# 중간값의 값보다 찾고자 하는 값이 작거나 같은 경우 왼쪽 확인
	elif array[mid] >= target :
		return first(array, target, start, mid - 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, mid - 1)
	# 중간점의 값보다 찾고자 하는 값이 크거나 같은 경우 오른쪽 확인
	else :
		return last(array, target, mid+1, end)

n, x = map(int, input().split()) # 데이터의 갯수 N, 찾고자 하는 값 x
array = list(map(int, input().split()))

# 값이 x인 데이터의 갯수 계산
count = count_by_value(array, x)

# 값이 x인 원소가 존재하지 않는다면
if count == 0 :
	print(-1)
# 값이 x인 원소가 존재한다면
else :
	print(count)

이진탐색 라이브러리 bisect 활용 코드

from bisect import bisect_left, bisect_right

# 값이 [left_value, right_value] 인 데이터의 갯수를 반환하는 함수
def count_by_range(array, left_value, right_value) :
	right_index = bisect_right(array, right_value)
	left_index = bisect_left(array, left_value)
	return right_index-left_index

n, x = map(int, input().split()) # 데이터의 갯수 N, 찾고자 하는 값 x
array = list(map(int, input().split()))

# 값이 [x, x] 범위에 있는 데이터의 갯수 계싼
count = count_by_range(array, x, x)

# 값이 x인 원소가 존재하지 않는다면
if count == 0 :
	print(-1)
# 값이 x인 원소가 존재한다면
else :
	print(count)