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

문제

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

코딩테스트 연습 - 입국심사

 

접근법

정답이 될 수 있는 범위는 0 부터 times 배열의 최대값 * n 이 된다.

입출력 예시로 보면 심사하는데 걸리는 시간은 7과 10이 있다.

이때 6명의 사람을 심사하는데 최악의 경우는 모든 사람이 10이 걸리는 심사대에서 심사를 받는 것이다.

그렇게 되면 6 * 10, 즉 최대 60의 시간이 걸린다는 것을 알 수 있다.

그럼 정답은 0~60 사이에 있다는 것을 알게 되었으므로 0~60사이를 이분 탐색하였다.

isPossible() 메소드는 해당 시간내에 모든 사람들 심사할 수 있는지를 판별하여 boolean을 리턴해준다.

0~60을 이분탐색하면서 가능한 값을 answer에 저장해주면서 진행한다.

 

코드

class Solution {
    private int[] times;
    
    public long solution(int n, int[] times) {
        long answer = Long.MAX_VALUE;

        this.times = times.clone();

        long max = 0;
        for(int i=0;i<times.length;i++){
            max = Math.max(times[i], max);
        }

        long low = 0;
        long high = max * n;
        while(low <= high){
            long mid = (low + high) / 2;
            if(isPossible(mid, n)){
                answer = Math.min(answer, mid);
                high = mid-1;
            }else{
                low = mid+1;
            }
        }

        return answer;
    }

    private boolean isPossible(long mid, long n) {

        for(int time : this.times){
            n -= mid / time;
            if(n<=0)
                return true;
        }

        return false;
    }
}