프로그래머스, 레벨3, 입국심사

입국심사.

문제:

입국하는 사람수 : n

심사대 :[심사시간, 심사시간..]

으로 하여 최소 입국 심사 시간을 구하는 것이다.

예를 들어 6, [7,10] 일 경우, 6명을 2개의 심사대에서(7분, 10분 심사 걸림) 심사를 할 경우 제일 빠른 경우가 언제인지를 알아내야한다.

이진탐색 문제로 분류가 되어있는데 처음에 풀때는 이걸 그렇게 접근 못했고 결국 다른 사람들의 해설을 확인할 수 밖에 없었다.

이 문제를 처음에는 동적계획으로 풀거나 아니면 횟수 구분을 통한 변수 조절 등.. 다르게 생각해봤는데 사실상 손으로도 풀리지가 않아서...

핵심은 다음과 같다.

위 예시의 경우 최악의 시간은 60분이다.(6명이 전부 10분 걸리는 심사대로 갔을 경우를 뜻한다)

그리고 상징적인 값인 1분을 상정한 후 1분과 60분 사이의 중간값, 30분을 정한다.

이제 우리에겐 30분이란 시간이 있으니 이 30분 동안 과연 몇명을 입국심사 할 수 있는지 계산 해본다.

계산 방법은 단순하다. 30분 // 7 + 30분 // 10이면 된다. 

즉 30분 동안 7분 심사대는 4명을 심사할 수 있고 10분 심사대는 3명을 심사할 수 있으므로 총 7명을 해결 할 수 있다.

그렇다면 다시 문제로 돌아가보자. 문제에서는 6명이 대기자로 제시되어있다.

우리는 30분의 시간동안 7명을 심사 할 수 있다. 7명 > 6명, 즉 30분은 매우 충분한 시간이다.

그렇다면 우리는 30분보다 작은 값을 주고 똑같은 방법을 통해서 해당 시간이 해결할 수 있는 인원수를 구해볼 수 있다.

제일 처음에는 1, 30, 60이었으나 이제는 시간을 줄여야 하므로 1, ?, 30이 된다.

그럼 이제 중간 값은 15가 되고 15 //7 + 15// 10 은 3명이 된다.

3명은 6명에 한참 모자라므로 15분이란 시간은 매우 부족한 시간임을 알 수 있다.

이제는 15, ? , 30이 된다. 

중간값은 22가 될 것이고 22분 동안 해결할 사람 수는 22//7 + 22//10, 5명이 된다.

이 역시 매우 부족하므로 시간이 더 필요하다

이제는 22 ? 30 이 될 것이고 중간 값은 26, 26분동안 해결할 사람 수는 26 //7 + 26//10으로 5명이 된다.

아직도 부족하다

26 ? 30에서 중간 값은 28이 된다. 28//7 + 28//10 은 6명이다.

6명은 문제에서 제시한 사람수이다!! 그런데 혹시 모르니 27로도 해보자...

이런 방식으로 이 문제를 풀면 된다.

결국 최악의 시간(max_time)으로 부터 아래로 줄여가면서 해당 시간대가 소화할 수 있는 사람수를 찾는 것이고

하나씩 내리게 되면 O(N) 시간이 들지만 이진탐색을 하게되면 O(logN)이므로 훨씬 빠르게 가능하기에 이진 탐색으로 접근 하는 것이다.

def solution(n, time):
    mid = n/2 * max(time) # 최악의 시간의 경우
    Left = 1
    Right = n * max(time)
    while Left <= Right:
        tot = 0
        for i in time:
            tot += mid // i
        if tot == n:
            temp_tot = 0
            for k in time:
                temp_tot += (mid-1)//k
            if temp_tot == n:
                return mid-1
            return mid
        if tot > n:
            Right = mid - 1
        else:
            Left = mid + 1
        mid = (Right + Left) // 2
        
if __name__ == "__main__":
    print(solution(6, [7,10]))

라고 해설을 위해서 썻지만 정작 내 코드는 실패만 주르극...아무래도 종료조건에 뭔가 다른게 더 필요해 보이는데..지금 내눈엔 안보인다.