이분탐색(이진탐색, Binary Search) / Python / 프로그래머스 입국심사

Binary Search(이진/이분 탐색)

출처 Wikipedia

• 이름에서 알 수 있듯이, 배열을 둘로 나누어 탐색하는 것이다.
• 정렬된 배열을 반으로 나누고, target의 값이 중앙값 보다 크면 탐색 시작지점을 중앙값 다음으로 옮기고, 작다면 탐색 종료 지점을 중앙값보다 이전으로 옮긴다.
• 위의 과정을 target 값을 찾을 때까지 반복한다. 중앙값이 target값과 같다면 탐색을 종료한다.
• 시간복잡도는 O(logN)

코드로 구현해보기

  1. 배열을 정렬한다

  2. 시작점과 종료점을 설정하고, 중앙값을 계산한다.

  3. 중앙값을 타겟값과 비교한다

      3-1) 타겟값이 중앙값과 같다면 탐색을 종료한다.

      3-2) 타겟값이 중앙값보다 크다면 시작점을 중앙값 다음으로 옮긴다.

      3-3) 타겟값이 중앙값보다 작다면 종료점을 중앙값 이전으로 옮긴다.

 

While문으로 구현

# 배열 arr에서 target 값의 인덱스를 이분탐색으로 찾아보자
def binary_search1(arr, target):
	target_index = 0
	arr.sort() # 배열 정렬
	start = 0 # 시작점
    end = len(arr) - 1# 종료점
    
    
    while start <= end:
    	mid = (start + end) // 2 # 중앙값
        
        if arr[mid] == target:  # 타겟값을 찾았다면
        	target_index = mid # target의 인덱스 값은 mid
            break # 반복문 종료
            
        elif arr[mid] > target: # 타겟값이 중앙값보다 크다면
        	start = mid + 1 # 시작지점을 중앙값 다음으로 옮기기
            
        elif arr[mid] < target: # 타겟값이 중앙값보다 작다면
        	end = mid - 1 # 종료지점을 중앙값 이전으로 옮기기
	
    return target_index # target의 인덱스값 반환

 

 

재귀함수로 구현

def binary_search2(arr, target, start, end):
	if start > end: return None # 원소가 없을 경우
    
	mid = (start + end) // 2
    
    if arr[mid] == target: return mid # 타겟값을 찾았다면 반환
    
    elif arr[mid] > target: # 중앙값이 타겟값보다 크다면
    	binary_search2(arr, target, mid + 1, end)  # 시작점을 중앙값 다음으로 옮기기
    
    elif arr[mid] < target: # 중앙값이 타겟값보다 작다면
    	binary_search2(arr, target, start, mid - 1) # 종료점을 중앙값 이전으로 옮기기

 

 

문제 풀어보기

개념을 학습했으니 문제를 풀어보자. 문제는 프로그래머스의 입국심사이다. 아래의 링크 참고

https://school.programmers.co.kr/learn/courses/30/lessons/43238

프로그래머스

 

입국심사를 기다리는 사람이 n명, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 주어질 때 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 구하는 문제이다.

 

제약조건

• 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하
• 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하
• 심사관은 1명 이상 100,000명 이하

주어진 입력값이 꽤 크기 때문에 time을 1씩 증가시키며 완전탐색으로 푸는 것은 불가능하다. 시간초과로 오답처리되기 때문에 이분탐색으로 풀어야 한다.

 

문제 해결 아이디어

• target값은 심사시간의 최솟값이다.
• 최소 시간은 1분만에 n명의 사람이 모두 심사를 받을 수 있는 경우이다.
• 최대 시간은 심사 시간이 가장 긴 심사관이 n명의 사람을 모두 심사하는 경우이다.
• 최소/최대 시간의 중앙값을 임의의 심사시간으로 설정하고, 해당 시간에 심사를 받을 수 있는 사람이 몇명인지 계산한다.
• 심사를 받을 수 있는 사람이 n과 같은지, 큰지, 작은지 비교한다.
  
  • 심사를 받을 수 있는 사람이 n명이면 심사시간을 중앙값으로 설정한다.
  • 심사를 받을 수 있는 사람이 n명보다 많다면 최대 시간을 중앙값 이전으로 옮긴다.
  • 심사를 받을 수 있는 사람이 n명보다 적다면 최소 시간을 중앙값 다음으로 옮긴다.
• 심사시간 최솟값을 반환한다.

 

코드

def solution(n, times):
    times.sort() # 배열 정렬
    start = 1 # 최소 시간
    end = max(times) * n # 최대 시간
    result = 0
    while start <= end:
        mid = (start + end) // 2 # 중앙값
        # 주어진 시간(mid) 내에 입국 심사를 통과한 사람
        entrants = passedScreening(times, mid)
        
        if entrants >= n: # 심사를 통과한 사람이 n명 이상이라면
            result = mid # 결과값 설정
            end = mid - 1 # 최대 시간을 중앙값보다 줄이기
            
        elif entrants < n: # 심사를 통과한 사람이 n명 미만이라면
            start = mid + 1 # 최소 시간을 중앙값 다음으로 
            
    return result # 심사 시간 최솟값 반환
        
        
# 주어진 시간 내에 심사관마다 몇명을 심사할 수 있는지 계산 및 합계
def passedScreening(arr, time):
    return sum(time // a for a in arr)