[프로그래머스] 입국 심사 (Golang)

문제

프로그래머스 문제 입국심사

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

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

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

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

제한사항

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

접근

일반적으로 이렇게 범위가 넓은 경우 이진 탐색을 통해 문제를 해결할 수 있다.

다만 해당 경우에는 기다리는 사람 수도 최대 1,000,000,000명 걸리는 시간도 1,000,000,000분, 심지어는 심사관도 100,000명까지 존재하기 때문에 어떤 방식으로 접근해야 할 지 고민이 되었다.

아무리 생각해도 어떤 부분에서 접근을 해야 할 지 몰라 이번엔 ChatGPT에게 힌트를 요청해보았다. (사실 그래서 작성하는 반성의 포스팅이다)

ChatGPT의 힌트

답변을 요약하자면 return 값인 처리하는 데 걸리는 총 최소 시간을 기준으로 이분 탐색을 하라고 제안하고 있다. 처리하는데 걸리는 총 시간 / 각 심시관의 처리시간 은 처리하는 사람 수가 되기 때문에 이 부분을 기준으로 이분 탐색을 진행하면 될 것으로 힌트를 받았다.

이 경우 아까 고민했던 심사관 100,000의 배열은 모두 돌긴 해야한다. 필자의 경우 이정도는 부하가 좀 클 것이라 생각했는데, 앞으로 이 정도는 괜찮다고 생각하고 접근해야할 것 같다

그래서 이진 탐색의 기준을 처리하는 데 걸리는 총 최소 시간으로 잡고, 이진 탐색을 진행해보자.

보통 이진 탐색의 결과값이 이진 탐색의 대상이기 때문에, 앞으로 이런 문제에선 결과값을 기준으로 먼저 생각해보는 것이 좋을 것 같다

구현

먼저 이진 탐색 기준이 되는 canHandled() 함수를 작성했다. 해당 함수는 처리하는 데 걸리는 총 최소 시간을 기준으로 처리하는 사람 수를 구하는 함수이다.

해당 함수의 용도는 이진 탐색 분기마다 조건을 확인위한 용도로 사용된다.

func canHandled(times []int, time int64, human int) bool {
	var total int64 = 0
	
    for _, t := range times {
		total += time / int64(t)
	}
    
	return total >= int64(human)
}

이후 해당 함수를 이용해 이진 탐색을 실제로 진행하는 코드를 작성한다.

func solution(n int, times []int) int64 {
    maxTime := int64(1000000000) * int64(n)
    minTime := int64(1)
    answer := int64(0)
    for minTime <= maxTime {
        mid := (minTime + maxTime) / 2
        if canHandled(times, mid, n) {
            maxTime = mid - 1
            answer = mid
        } else {
            minTime = mid + 1
        }
    }
	
    return answer
}

canHandled() 함수의 결과가 true일 경우, 처리하는 사람 수가 n보다 크거나 같다는 의미이므로, maxTime을 줄여준다. 반대로 false일 경우에는 처리하는 사람 수가 n보다 작다는 의미이므로, 다음 스테이지에서 더 많은 사람을 확보하기 위해 minTime을 늘려준다.

여기서 canHandled()가 true일 때만 answer를 갱신하는데 당연히 처리 가능한 시간이므로, 처리가 되지 않을 때는 answer를 갱신할 필요가 없다.