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

문제 설명

n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.

처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.

모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.

입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.

제한사항

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

입출력 예

n        times             return

6

[7, 10]

28

입출력 예 설명

가장 첫 두 사람은 바로 심사를 받으러 갑니다.

7분이 되었을 때, 첫 번째 심사대가 비고 3번째 사람이 심사를 받습니다.

10분이 되었을 때, 두 번째 심사대가 비고 4번째 사람이 심사를 받습니다.

14분이 되었을 때, 첫 번째 심사대가 비고 5번째 사람이 심사를 받습니다.

20분이 되었을 때, 두 번째 심사대가 비지만 6번째 사람이 그곳에서 심사를 받지 않고 1분을 더 기다린 후에 첫 번째 심사대에서 심사를 받으면 28분에 모든 사람의 심사가 끝납니다.

---

[접근]

머리로는 알겠는데 구현으로 옮기기 정말 어려운 문제였다

최대 심사 시간이 가장 작은 경우를 만드는게 핵심이었는데, 어차피 times 중 한 값의 배수니까... 까지 생각하고

어떤 값을 이분탐색해야할지 몰라 한참 헤맸다. 머리를 싸매다가 결국 다른분의 접근을 참고하였다.

 

1.최소시간, 최대시간을 start, end 로 설정한다.

2. 이를 이분탐색하여 mid 값 마다 각 times 로 나눈 누적합을 구한다

(ex. mid가 28분이면 7분심사대 4명, 10분심사대 2명 => 총 6명 심사 가능)

 

처음코드(오답)

def solution(n, times):
    answer = 0
    # allt = []
    # for t in times:
    #     for i in range(1,n+1):
    #         allt+=[t*i]
    # allt.sort() times의 모든 시간들의 배수 배열 정렬하면 시간초과됨..
    start = 1
    end = max(times)*n
    while start<=end:
        total = 0
        mid = (start+end)//2
        for t in times:
            total+=mid//t
        if total <=n:
            start = mid+1
        if total >n :
            end = mid -1
        answer = start
        
    #최악심사시간을 max로 두고, 최소 심사 min
    return answer

 

위 코드처럼 하면 자꾸 29 가 출력된다.

times 중 하나라도 나눠 떨어지는 값이어야 한다는 생각이 들어

조건을 이리저리 주고, times 의 배수들로 배열을 만들어 보았으나

해당 TC 만 통과하고 채점에서 시간초과를 받았다. 

 

알고보니 이분탐색의 조건이 잘못되었다.

 

def solution(n, times):
    answer = 0
    start = 1
    end = max(times)*n
    while start<end:
        total = 0
        mid = (start+end)//2
        for t in times:
            total+=mid//t
        if total <n:
            start = mid+1
        if total >=n :
            end = mid
        answer = start
        
    return answer

이분탐색 while 문에서 조건에서 등호가 빠지고, mid 가 아닌 start 를 반환하게 바뀌었더니 통과가 됐다.

 

아마도 최소시간을 구하는 문제이기 때문에 나처럼 29 와 같이 7이나 10으로 나눈 몫의 합이

n 과 일치하는 더 큰 수가 생기기 때문 아닐까 싶다. start의 경우 심사할 수 있는 인원보다 적은 경우 계속 mid+1을 해주고, 많거나 같은 경우에는 end에 mid를 대입하므로, 조건을 만족하는 최소값은 start 가 되는 것이다.

 

뭐랄까 아직도 촉으로는 이해했으나 정확하게 설명하기 힘든 문제인 것 같다.

통나무 베기 문제처럼 어떤 값을 이분탐색해야할 지 모를때 되새겨보면 좋을 듯 하다.