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

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

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

import java.io.*;
import java.util.*;

class Solution {
    public long solution(int n, int[] times) {
        long min = Long.MAX_VALUE;
        
        Arrays.sort(times);
        long left = 0;
        long right = 0;
        long mid;
        
        for (int time : times) {
			if (time > right) {
				right = time;
			}
		}
        
        right *=n;
        
        while(left<=right) {
            mid = (left + right) / 2;
            
        	long num = checkTime(mid, times);
        	
        	if(num < n) left = mid+1;
        	else {
                min = Math.min(min, mid);
                right = mid-1;
            }
        	
        }
        
        return min;
    }

	private long checkTime(long mid, int[] times) {
		long sum =0;
		
		for(int i=0; i<times.length; i++) {
			sum += mid/times[i];
		}
		
		return sum;
	}
}

정리

• 제한사항의 최대 값이 1,000,000,000 이기 때문에 이분 탐색을 통해 모든 사람이 심사를 받을 수 있고(n이상) 최솟값을 갖는 시간을 찾으면 된다.
• right의 설정은 (가장 오래 심사가 걸리는 시간 * 인원수)이다.
• mid 값을 설정해주고 현재 mid가 가리키고 있는 시간을 체크한다.
• 예) mid == 14일 경우 최대로 받을 수 있는 입국심사 인원은 3명이 된다.
• 최솟값을 저장하면서 left와 right가 교차할 때까지 반복한다.