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

https://school.programmers.co.kr/learn/courses/30/lessons/43238

프로그래머스

 

문제의 힌트는 제약사항에서 확인할 수 있습니다.

결국 기다리는 사람은 최대 10억명이므로 각각의 대기자에 대해서 문제를 해결할 순 없습니다.

 

결국 심사관 관점에서 문제를 풀어야함을 알 수 있고 문제가 결국 가장 효율적으로 심사하는 시간의 최솟값을 구하는 문제라는 것에 주목한다면, 최적화문제를 결정문제로 바꾸는 Parametric Search를 생각해볼 수 있습니다.

 

심사관이 심사하는데 걸린 소요시간을 T라고 했을 때, 이 T를 각각 심사관의 소요시간으로 나눈 값들의 합을 n과 비교하는 방식으로 문제를 해결할 수 있습니다.

 

n명의 사람에 대해서 처리가 가능하다면 right 포인터 위치를 mid위치로 옮기고 처리가 불가능하다면(n보다 작다면) left포인터 위치를 mid + 1로 이동시킵니다.

 

[코드]

import java.util.*;
class Solution {
    public long solution(int n, int[] times) {
        
        Arrays.sort(times);
        long left = 0;
        long right = (long) times[times.length - 1] * n;
        
        while(left < right){
            
            long mid = (left + (right - left) / 2);
            if(throughput(mid, times) >= n)
                right = mid;
            else
                left = mid + 1;
        }
        return left;
    }
    
    long throughput(long totalTime, int[] times){
        long ret = 0;
        for(int i=0; i<times.length; i++){
            ret += totalTime / times[i];
        }
        return ret;
    }
}