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

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

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

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

풀이

심사를 받는데 최소로 소요되는 시간을 반환하는 문제로 소요되는 시간을 기준으로 이분탐색을 하였다.

 

우선 제일 오래 걸리는 심사위원을 알아내기 위해 times를 정렬해 주었다. 그리고 제일 오래걸리는 심사위원의 시간을 알아내어 최대 시간을 계산해 주었다.

 

이때 최대 소요 시간이란, 제일 오래걸리는 심사위원이 n명 모두를 심사할때 소요되는 시간이 되므로

times[times.length - 1] * n이 된다.

 

최소로 소요되는 시간은 문제의 조건에 따라 1이된다. 심사위원을 1명 이상이고, 심사를 기다리는 사람도 1명 이상이고, 심사관이 한 명을 심사하는데 걸리는 시간도 1분 이상이기 때문이다.

 

이에 따라 start는 1로 잡고, end는 위와 같이 잡아주었다.

 

다음으로 mid를 구하고 mid시간이 되었을때 각 심사위원이 심사할 수 있는 인원의 총합을 구하여 총 합이 n보다 크거나 같다면 큰 부분을 탐색하고, 작다면 작은 부분을 탐색하도록 하였다.

코드

import java.util.*;
 
class Solution {
    public long solution(int n, int[] times) {
        Arrays.sort(times);
        
        long answer = 0;
        long start = 1;
        long end = (long)times[times.length - 1] * n; //제일 오래걸리는 심사위원이 모든 사람을 심사하는 경우
        while(start <= end) {
            long mid = (start + end) / 2;
            
            long total = 0;
            for(int i = 0; i < times.length; i++) {
                total += (long)(mid / times[i]); // mid시간이 됬을때 각 심사위원이 몇명을 심사할 수 있는지를 더한다.
            }
            if(total >= n) {
                end = mid - 1;
                answer = mid;
            } else {
                start = mid + 1;
            }
        }
        return answer;
    }
}