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

프로그래머스 입국심사

문제풀이

기본적인 이분탐색 문제였다. 이분탐색 문제는 제한사항에 주어지는 숫자가 굉장히 크고 최댓값 또는 최솟값을 구하는 경우가 많다. 이 문제에서는 모든 인원이 입국심사를 통과할 수 있는 시간의 최솟값을 구하는 문제다. 구성은 일반적인 형태를 띄고있고 다음과 같은 부분을 주의하면 된다.

• 초기값은 left = 1, right = 가장 오래걸리는 심사관이 모든 사람을 심사하는 시간
• 현재 시간(mid)에 각 심사관들이 심사할 수 있는 최대 인원을 모두 합한 값과 주어진 전체 인원과 비교

구현코드

import java.util.*;

class Solution {
    public long solution(int n, int[] times) {
        Arrays.sort(times);
        return binerySearch(times, n, times[times.length - 1]);
    }
    
    long binerySearch(int[] times, int n, long max){
        long left = 1, right = max * n;
        long mid = 0;
        long ans = Long.MAX_VALUE;

        while(left <= right){
            mid = (left + right) / 2;
            
            if(isPassed(times, n, mid)){
                ans = ans > mid ? mid : ans;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
    
    boolean isPassed(int[] times, int n, long mid){
        long amount = 0;
        
        for(int i = 0 ; i < times.length ; ++i){
            amount += mid / times[i];
        }
        
        if(amount >= n) return true;
        else return false;
    }
}