프로그래머스 이진탐색 Level 3 (입국심사)

문제

---

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

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

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

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

 

 

 

제한사항

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

 

 

 

풀이

---

이 문제를 이분 탐색 풀이 법에 대해 의문이 있었다.

 

수학적인 접근을 하였다.

예시에서 주어진 경우를 보면

n	times	return
6	[7, 10]	28

 

7 * 4 = 28

10 * 2 = 20 시간은 더 걸린 것이 중요하므로 28분이 된다.

 

여기서 4명과 2명을 나누는 기준을 생각해 보다.

28 / 7 = 4

28 / 10 = 2 라는 것에 집중을 했다.

 

28이라는 시간을 주고 얼마나 사람을 심사를 할 수 있는지를 판단하여 n 보다 큰지 작은지, 이진탐색을 이렇게 사용하면 되겠다 싶었다.

 

여기서 얻어낸 식은 아래와 같다.

추정시간 / 심사관의 심사시간 = 추정시간동안 심사관이 처리할 수 있는 입국심사자 수

이 식을 이용하여 이분 탐색을 하였다.

우선 times의 배열을 오름차순으로 만든다.

Arrays.sort(times);

 

 

이후 left, right 값을 정해준다. right 값은 제일 오래걸리는 시간 즉, 처리시간이 제일 긴 심사관이 혼자서 모든 인원을 처리했을 때의 시간이다.

long answer = (long)times[times.length - 1]  * n;
long left = 1;
long right = answer;

 

이후는 우리가 아는 이진탐색을 해주면 된다.

해당 시간에 처리할 수 있는 입국심사자수를 n 과 비교하여 크다면 right 값을 바꿔주고, 작다면 left 값을 바꿔주면 된다.

if(sum < n){
	left = mid + 1;
}
else{
	answer = Math.min(answer, mid);
	right = mid - 1;
}

 

<전체 코드>

import java.util.*;
import java.io.*;

class Solution {
    public long solution(int n, int[] times) {
        Arrays.sort(times);
        long answer = (long)times[times.length - 1]  * n;
        long left = 1;
        long right = answer;
        
        while(left <= right){
            
            long mid = (left + right) / 2;
            long sum = 0;
            
            for(int i = 0 ; i < times.length ; i++){
                sum += mid / times[i];
            }
            
            if(sum < n){
                left = mid + 1;
            }
            else{
                answer = Math.min(answer, mid);
                right = mid - 1;
            }            
        }

        return answer;
    }
}