[프로그래머스] 입국심사(이분탐색)

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

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

 

이분탐색으로 푸는 문제입니다. 

문제부터 간단하게 요약하면, 

 

입국 심사를 기다리는 사람들이 times라는 array안의 element만큼의 시간이 각각 걸리는 심사위원들에게 심사를 받을 때, 가장 빠른 시간안에 모든 사람들이 심사를 받게 할 수 있는 시간을 구하는 것입니다. 

 

예시입니다. 6명의 사람들이 2명의 심사위원에게 심사를 받을 때 걸리는 최소 시간은 28입니다. 여기에서 중요한 문제는 본문을 읽어보면 알겠지만, 이미 한 심사대가 비었지만 다른 심사대를 기다렸을 때 종료시간이 더 빠르면 그곳으로 가서 심사를 받을 수도 있다는 것입니다. 

 

만약 5시간이 걸리는 심사대에 다른 사람의 심사가 4시간동안 진행되는 중에 15시간이 걸리는 심사대가 비면, 당연히 5시간이 걸리는 심사대를 기다렸다가 들어가는 것이 더 빠릅니다. 

 

여기에서 이 문제가 헷갈릴 수 있는데, 사람들은 위의 예시처럼 본인이 가장 빠르게 마치는 것이 중요한 것이 아닙니다. 모든 사람들의 종료 시간이 빨라지는 것이 중요합니다. 한마디로, 모든 사람들의 빠른 종료를 위해 위의 상황에서도 15시간이 걸리는 심사대로 들어 갈 수 있다는 것입니다. 

본문에서 이야기 했듯, "기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다"이기 떄문에, 가능성에 대한 언급만이 주어진 상황입니다. 

 

결과적으로 solution(n, times)에 

n : 입국심사를 기다리는 사람수

times : 각 심사관이 한명 심사하는데 걸리는 시간

이 input으로 들어갈 때 

 

모든 사람들이 종료되는 최솟값 시간을 return하여야 합니다. 

 

<Solution>

이 문제의 아이디어는 시간을 이분탐색 하여야 합니다. 

 

예시를 들어 아이디어를 설명해 보겠습니다. 

우선 최소 시간은 (1)입니다. 그리고 최대 시간은 (times array의 max 값 * 사람수) 입니다. (모든 사람들이 가장 오래걸리는 심사위원의 심사를 받을 때) 

이렇게 min과 max의 값을 두고, 중간의 값이 가능한지 판단합니다. 

 

예를 들면, 

solution(2, [2,5])라는 상황을 생각해봅시다. 

min = 1

max = 2*5 = 10

으로 둡니다. 

 

<현재 min : 1, max : 10>

다음으로 이분탐색을 하게 되면, 5라는 중간값이 나오게 되고, 이 5를 이용해 이것이 가능한 값인지 불가능한 값인지 판단합니다. 

[2, 5]의 심사위원 array와 5라는 시간을 생각해봅시다. 5라는 시간동안 첫번째 심사위원은 2명의 사람을 판단할 수 있고, 두번째 심사위원은 3명의 사람을 판단할 수 있습니다. 이는 우리가 판단해야하는 사람수인 2명 이상이기 때문에 이 경우 가능합니다. 그렇기 때문에 max값을 5로 만들어 줍니다. 

 

<현재 min : 1, max : 5>

다음으로 이분탐색을 하게 되면, 3이라는 중간값이 나오게 되고 마찬가지로 판단해봅시다. 

[2,5]의 심사위원은 각각 1명, 0명을 판단할 수 있습니다. 이는 우리가 판단해야하는 사람수인 2명보다 적습니다. 그래서 

min값을 3으로 만들어 줍니다.

 

<현재 min : 3, max : 5>

다음으로 이분탐색을 하게 되면, 4이라는 중간값이 나오게 되고 마찬가지로 판단해봅시다. 

각각의 심사위원은 2명, 0명을 판단할 수 있습니다. 우리가 판단해야 하는 사람수인 2명과 일치합니다. 그러면 이 때 이 4라는 시간이 우리가 구하는 최소의 시간이라고 말할 수 있을까요?

4보다 적은 시간이 가능 할 지도 모릅니다. 그래서 계속 탐색을 진행하기 위해서는 사람수가 같아지는 경우들에 대해서도 마치 더 큰 값인 것 처럼 취급해 주어야 합니다. 

(혹시 이해가 어렵다면 10,11,12,13의 시간에서 판단할 수 있는 사람수가 만약 모두 같고, 이분탐색 과정에서 12라는 값을 얻게 되었으면, 그 값을 바로 return하면 안되고 10을 return해야하기 때문에 12를 max값으로 놓고 계속 탐색을 진행한다는 이야기 입니다)

 

이처럼 판단을 하고, 끝나는 상황(min과 max값이 1차이밖에 안나는경우)

if ((max_t + min_t)//2 == min_t):

에서는 min값 혹은 max값 둘중하나가 결과가 되므로 

확인후 return 해줍니다.

 

실제 구현은 아래와 같습니다.

 

def available(n, times, t): # can evaluate n people within t time
    temp = 0
    for time in times:
        temp+= t//time
        if temp >=n:
            return 1
        else : 
            continue
    return 0

def solution(n, times):
    max_t = max(times)*n
    min_t = 1

    def search(min_t, max_t):
        # when will it return? 
        if ((max_t + min_t)//2 == min_t):
            if available(n, times, min_t):
                return min_t
            else:
                return max_t

        mid_t = (max_t + min_t)//2
        flag = available(n, times, mid_t)

        if flag == 1:
            return search(min_t, mid_t)
        else : # flag == 0
            return search(mid_t, max_t)

    return search(min_t, max_t)