[Binary Search] 입국 심사 - 프로그래머스

https://programmers.co.kr/learn/courses/30/lessons/43238?language=python3 

코딩테스트 연습 - 입국심사

 

Example

6명의 사람이 있고

7, 10의 경우를 생각해보면

시간을 1≤ t ≤ 60(6명*10분) 범위 내에서 선택해서 적용한다 가정하면

 

예를 들어 중간 값인 30분을 할당할 수 있다고 하면

7의 경우 4명을 담당할 수 있고

10의 경우 3명을 감당할 수 있다.

따라서 각자 담당할 수 있는 사람의 합은 7명이고 이는 6명보다 더 큰 수가 된다

이 경우 시간이 많이 할당되므로 더 줄이는 방향으로 간다

 

반면 그 중간 값인 15분을 고려하면

7의 경우 2명을 담당, 10의 경우 1명을 담당하므로 3명을 총 담당이 가능하므로 6명을 주어진 시간에 다 담당 불가

따라서 시간을 더 늘리는 방향으로 갈 수 있다. → 이 search를 이분 탐색을 이용한다!

 

시도 1

def binary_search(L, U) : 
	mid = (L+U)//2
	return mid

def make_sum(time, times, n) : 
	sums = 0
	for i in times : 
		sums += (time)//i
		if sums == n : 
			return sums ## 예시 5 [1, 5, 10], heuristic

def solution(n, times) : 
	answer = max(times)*n
	mins = 1
	maxs = max(times)*n
	while maxs-mins != 1 : 
		time = binary_search(mins, maxs)
		sums = make_sum(time, times, n)
		if sums > n : maxs = time
		elif sums < n : mins = time
		else : 
			answer = min(time, answer)
			maxs = time
	return answer

여기 종료 조건을 max-min으로 했는데

binary search의 무한 루프를 막기 위한 조건이 확실치가 않음!

질문하기를 뒤져보니!

풀리지 않는 반례들이 존재!!

 

6

[4, 10]

이 경우의 답은 20인데

저 알고리즘으로는 절대 20이 나올 수 없음!

 

시도 2

그래서 저 경우를 Special Case로 다루어보고자 함!!

max와 min이 1차이가 나서 답을 슬슬 내야 되는 상황에서 최적의 해를 내지 못한느 경우는

그 경우 모든 인원을 수용할 수 있는 최소의 경우는 심사위원당 맡은 수의 사람의 합이 n보다는 큰 수 중 가장 작은 수여야 한다!

 

def binary_search(L, U) : 
    mid = int((L+U)/2)
    return mid
def make_sum(time, times, n) : 
    sums = 0
    for i in times : 
        sums += (time)//i
        if sums == n : ## 대표 예제 n=5, [1, 5, 10]
            return sums
    return sums
def solution(n, times):
    answer = max(times)*n
    mins = 1
    maxs = max(times)*n
    while maxs-mins != 1 : 
        time = binary_search(mins, maxs)
        sums = make_sum(time, times, n)
        if sums > n : maxs = time
        elif sums < n :mins = time
        else : 
            answer = min(time, answer)
            maxs = time
    if answer == max(times)*n: ## 대표 예제 n=6, [4, 10], n=5, [1, 5, 10]
        answer = maxs
    return answer

원래 binary search는 Lower bound와 Upper bound 역전 내지 같아질 때가 종료조건이니

이것을 고려해주는 것이 중요

그리고 search할 때마다 폭을 줄여주기 위해

maxs = time-1

mins = time+1 같은

조치를 취해주었으면 더 좋았을듯