[이것이 코딩테스트다] 16일차 - 이진탐색 예제 | 정렬된 배열에서 특정 수의 개수 구하기

본문은 [이것이 취업을 위한 코딩테스트다 - 나동빈] 책을 공부하고 작성한 글입니다.

Chapter 7 이진탐색

오늘 풀이한 문제 - 실전문제 풀이

[이코테 368p] 정렬된 배열에서 특정 수의 개수 구하기

문제

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

 

입력 예시
7 2
1 1 2 2 2 3

출력 예시
3

 

접근방법

시간복잡도 O(logN)을 보고 이진 탐색으로 풀어야 한다는 것을 알았다!

이진탐색을 하나만 사용하려니 어떻게 해야할지 고민이 많았는데 이진탐색을 두번사용하면 된다는 힘트를 얻어 코드를 구상해보았다

이진탐색을 할때 조건문을 또 헷갈렸다 ,, 조건문이 어려울때가 종종있다

## target이 시작하는 곳 찾기
def bs_start(start, end, data, target):
    mid = (start+end)//2
    if start >end:
        return None
        
    ## 현재 위치가 target이고 현재 지점이 시작점이거나, 바로 앞의 값이 target보다 작을때 (target이 아닐때)
    if data[mid] == target and (mid == 0 or data[mid-1] < target):
        return mid
        
    ## 현재위치가 target보다 크거나 같을때 end 위치 변경 (최초 값을 찾아가기 때문)
    elif data[mid] >= target:
        return bs_start(start, mid-1, data, target)
    
    ## 현재위치가 target보다 작을때 start 위치 변경
    else:
        return bs_start(mid+1, end, data, target)

## target이 끝나는 곳 찾기
def bs_end(start, end, data, target):
    mid = (start+end)//2
    if start >end:
        return None
        
     ## 현재 위치가 target이고 현재 지점이 끝이거나, 바로 뒤의 값이 target보다 클때 (target이 아닐때)
    if data[mid] == target and (mid == end or data[mid+1] > target):
        return mid
    
    ## 현재위치가 target보다 클때 end 위치 변경 
    elif data[mid] > target:
        return bs_end(start, mid-1, data, target)
    
    ## 현재위치가 target과 같거나 작을때 start 위치 변경 (끝점을 찾아가기 때문)
    else:
        return bs_end(mid+1, end, data, target)
        
n,x = 7,2
data = [1,1,2,2,2,3]
start = 0
end = n-1 

first = bs_start(start, end, data, x)
last = bs_end(start, end, data, x)

print (last - first +1)

파이썬 이진탐색 라이브러리를 사용하는 방법도 있다

## 이진탐색 라이브러리 사용하기
from bisect import bisect_left, bisect_right

n,x = 7,2
data = [1,1,2,2,2,3]


first = bisect_left(data, x)
last = bisect_right(data, x)

print(last-first)

이 라이브러리는 몰랐는데 종종 유용하게 쓰일것같아 외워둬야겠다

• bisect_left(data, x) : 정렬된 순서를 유지하면서 리스트 a에 데이터 x를 삽입할 가장 왼쪽 인덱스를 찾음
• bisect_right(data, x) : 정렬된 순서를 유지하도록 리스트 a에 데이터 x를 삽입할 가장 오른쪽 인덱스를 찾음
• 시간 복잡도 : O(logN)

from bisect import bisect_left, bisect_right

bisect_right 사용시 target의 맨끝 위치가 아닌 맨끝 바로 뒤 인덱스가 반환되니 주의하도록한다