[이진 탐색 알고리즘] 문제3 - 정렬된 배열에서 특정 수의 개수 구하기

[이코테] 문제3 - 정렬된 배열에서 특정 수의 개수 구하기

(한줄평) 라이브러리를 이용하면 쉽게 풀 수 있는 문제! 하지만 라이브러리를 사용하지 않고 푸는 법도 알아야 함

---

---

시간 복잡도 O(logN)을 요구하기 떄문에 일반적인 선형 탐색으로는 시간초과 판정을 받는다.

데이터가 오름차순 정렬되어 있기 떄문에 이진 탐색을 수행할 수 있다.

(풀이1) bisect 라이브러리 이용

풀이 시간: 15분 이내

1) 문제 해결 아이디어

특정 값이 등장하는 첫 번째 위치와 마지막 위치를 찾아 위치 차이를 계산해 문제를 해결할 수 있다.

bisect_left와 bisect_right를 이용해 각각의 위치를 구한다.

 

2) 소스코드

# 1. bisect 라이브러리 이용
from bisect import bisect_left, bisect_right

# 값이 [left_value, right_value] 범위에 있는 개수 반환
def count_by_range(array, left_value, right_value):
  left_idx = bisect_left(array, left_value)
  right_idx = bisect_right(array, right_value)
  return right_idx - left_idx

n, x = map(int, input().split())  # 원소 개수, 탐색값
array = list(map(int, input().split()))  # n개의 원소
# x인 원소의 개수
cnt = count_by_range(array, x, x)

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

(풀이2) 반복문을 이용한 이진 탐색

풀이 시간: 15분 이내

1) 문제 해결 아이디어

처음 탐색값을 발견하면 개수를 1 카운팅하고 그 위치에서 오른쪽, 왼쪽으로 탐색값이 더 있는지 확인하고 카운팅하는 방식이다.

38, 42줄에서 왼쪽, 오른쪽에 탐색값이 더 있는지 검사할 때 범위를 먼저 검사해주지 않으면 indexError가 나니 주의해야한다.

 

2) 소스코드

# 2. 이진 탐색
def binary_search(array, target, start, end):
  global cnt
  while True:
    # 시작점과 끝점이 엇갈리면 종료
    if start > end:  return -1
    mid = (start + end) // 2  
    # 1. 탐색값이 중간값보다 크면 오른쪽 탐색
    if array[mid] < target:
      start = mid + 1
    # 2. 탐색값이 중간값보다 작으면 왼쪽 탐색
    elif array[mid] > target:
      end = mid - 1
    # 3. 탐색값이 중간값과 같다면 왼쪽, 오른쪽 탐색
    else:
      cnt += 1
      left, right = mid - 1, mid + 1
      # 왼쪽에서 탐색값 더 찾기
      while left >= start and array[left] == target:  
        cnt += 1
        left -= 1
      # 오른쪽에서 탐색값 더 찾기
      while right <= end and array[right] == target:  
        cnt += 1
        right += 1
      return cnt
    
n, x = map(int, input().split())  # 원소 개수, 탐색값
array = list(map(int, input().split()))  # n개의 원소
cnt = 0  # 탐색값의 개수

print(binary_search(array, x, 0, n - 1))