[pro] 프로그래머스 level3 43238 입국심사 (Java) - 이분탐색

[문제]

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

프로그래머스

 

[풀이]

이전에 c++로 풀었던 적이 있다. (c++ 코드)

 

1.  (전체 심사 가능 인원) += (전체 심사 시간)/(심사관 당 심사시간)

따라서 전체 심사 가능 인원이 n명보다 크거나 같으면 전체 심사 시간을 줄여볼 수 있다.

반대로 n명보다 작으면 전체 심사 시간을 늘려서 n명을 충족할 수 있도록 해야 한다. 

2. n과 times의 범위가 모두 int 범위를 초과하므로 long으로 선언해야 한다.

최대 심사 시간은 가장 심사 시간이 오래 걸리는 심사위원이 n명을 모두 심사하는 경우이다. 

따라서 long high = (long)times[times.length-1] * n; 으로 쓸 수 있으며 이 때 int 값끼리 곱해서 int 범위를 초과하는 일이 발생하므로 long으로 명시적 변환 후에 곱하도록 주의해야 한다.

 

[코드]

 

import java.util.*;

class Solution {
    public long solution(int n, int[] times) {
        long answer = 0;
        // 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return
        
        Arrays.sort(times);
        long low = 1;
        long high = (long)times[times.length-1] * n;
        
        while(low<=high){
            long mid = (low+high)/2;
            long sum = 0;
            for(int i=0; i<times.length; i++){
                sum += mid/times[i];
            }
            
            if(sum >= n){
                answer = mid;
                high = mid-1;
            }
            else{
                low = mid+1;
            }
            
        }        
        return answer;
    }

}