[프로그래머스] Lv3. 입국심사

🔗

풀이

입국 심사를 기다리는 사람이 최대 10억명이고 심사관은 최대 10만명이기 때문에 매 분에 대해서 어떤 심사관에게 심사를 받아야 최소가 되는지 완전 탐색으로 구하는 것은 시간초과가 발생한다. 우선 해당 조건을 활용하면 각 심사관의 최대 심사 시간은 10억이고 입국심사를 기다리는 사람도 최대 10억이므로 모든 사람이 심사를 받는데 걸리는 시간의 최대는 10억 x 10억이 된다는 것을 알 수 있다. 이를 활용해서 이분 탐색으로 심사를 받는 데 걸리는 시간을 정해놓고 해당 시간이 모든 사람이 심사를 받을 수 있다는 조건을 만족할 수 있는지 여부를 확인하면서 최소값을 찾아나가는 방법으로 문제를 풀 수 있다.

최대는 10억 x 10억 분이고 최소는 1 분이다. 해당 시간 만큼 주어졌을 때 모든 사람이 심사를 받을 수 있는지 여부를 확인하면 된다. binarySearch() 함수를 통해서 해당 조건을 통과하는지 여부를 확인하게 된다. 우선 심사관들이 심사하는데 걸리는 시간을 오름차순 정렬한다. 시간이 적게 걸리는 사람이 더 많은 사람을 심사할 수 있기 때문이다. 만약 30분이 주어진다면 심사하는데 7분이 걸리는 심사관은 4명을 심사할 수 있고, 10분이 걸리는 사람은 3명만 심사할 수 있다. 이런 식으로 각 심사관의 심사 시간에 대해 몇 명을 심사할 수 있는지 계산하고 해당 사람의 수가 주어지는 사람의 수 n명을 제한 시간내에 맞출 수 있다면 조건을 통과한 것이다. 즉 주어지는 시간으로는 모든 사람을 심사할 수 있는 시간이 충분히 되므로 문제의 조건에 맞도록 최소값을 찾으면 된다. 최소값을 찾기 위해서는 이분 탐색의 범위를 작은 값쪽으로 맞춰주면 된다.

만약 조건을 만족하지 않는다면 조건을 만족할 수 있도록 심사 시간을 늘려야 하므로 이분 탐색의 범위를 큰 값쪽으로 옮기면 된다.

import java.util.*;

class Solution {
    public boolean binarySearch(long n, int[] times, long limitTime) {
        for (int time : times) {
            if (time > limitTime) break;
            n -= (limitTime / time);
            
            if (n <= 0) return true;
        }
        return n <= 0;
    }
    
    public long solution(int n, int[] times) {
        Arrays.sort(times);
        long maxTime = 1_000_000_000_000_000_000L - 1L;
        long minTime = 1L;
            
        long midTime;
        while (minTime <= maxTime) {
            midTime = (maxTime + minTime) / 2L;
            
            if (binarySearch(n, times, midTime)) {
                maxTime = midTime - 1L;
            } else {
                minTime = midTime + 1L;
            }
        }
        
        return minTime;
    }
}