이분탐색 - 입국심사

 

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

 

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

 

문제풀이

times 배열의 최고 값을 기준으로 이분탐색하면서 mid값으로 각 심사관이 몇명을 검색할 수 있냐만 계산하면 최소값을 구할 수 있다.

 

max는 times가 오름차순으로 정렬 됬을 때, times[times.length-1] (가장 뒤) 에서 n 명 만큼 곱하면 된다. 이게 최악의 경우의 수인 max값이 된다.

 

이제 mid를 구하기 위해서 min 과 max를 비교하면서 반복한다. min이 max를 넘어가는 순간 while문은 종료가 된다.

 

max 와 min의 범위를 게속 줄여가면서 min값을 수정하고 해당 mid값으로 times 배열의 시간 값을 가진 심사관들이 몇명을 심사할 수 있는지 sum으로 합한다.

 

여기서 sum이 n보다는 당연히 크거나 같아야 한다. 작으면 시간안에 검색을 못한다는거니까 볼 것도 없다. 만약 크거나 같을경우, answer을 mid값으로 갱신을 시켜주면 된다.

 

import java.util.*;

class Solution {
    public long solution(int n, int[] times) {
        Arrays.sort(times);
        long min = 1;

        // times 배열의 최악의 경우는 범위
        // n명 기준으로 times의 가장 마지막 시간까지 탐색하는 경우.
    	long max = (long) times[times.length-1]*n;
    	long mid = 0;
    	long sum;
    	long answer = max;

    	while(min <= max) {
    		sum = 0;
    		mid = (min + max) / 2;

    		for(int time : times) {
    			sum += mid / time;
    		}

    		if(sum >= n) {
				answer = mid;
				max = mid - 1;
    		}
    		else {
    			min = mid + 1;
    		}
    	}


        return answer;
    }
}