[프로그래머스][Java] Lv.3 입국심사

풀이 방법 도출

기다리는 사람이 최대 1,000,000,000명, 심사하는데 걸리는 시간의 최댓값도 1,000,000,000분, 심사관 또한 100,000명으로 단순히 1초씩 더해가면서 반복문으로 풀이를 하기에는 시간초과가 날 것이 뻔한 문제입니다.

 

따라서 시간복잡도가 O(logN) 인 이분탐색으로 문제를 풀이할 것입니다.

---

풀이과정

1. 이분탐색을 위해 심사하는데 걸리는 시간의 최솟값과 최댓값을 세팅합니다.
   ( * return값이 long형이므로 최솟값과 최댓값 또한 long형으로 설정해주어야 합니다.)
2. while문으로 min이 max보다 커질 때까지 반복문을 수행합니다.
3. half에 min과 max의 중앙값을 넣고 해당 시간동안 모든 사람이 심사를 마칠 수 있는지 확인합니다.
4. 만약 심사를 마친 사람이 n보다 작다면, 모든 사람을 심사하지 못했으므로 시간을 늘려야 합니다.
5. half 이하의 시간으로는 모두 심사할 수 없으므로, 절반 이하는 버리고 min=half+1로 범위를 바꿔줍니다.
6. 하지만 만약 n이상의 사람을 심사할 수 있다면, answer값에 half값을 넣고 시간의 최솟값을 구하기 위해 범위를 max=half-1로 바꿔 검사를 진행합니다.
7. 결국 min>max가 되는 시점의 answer을 return 합니다.

---

전체 코드

import java.util.*;
class Solution {
    public long solution(int n, int[] times) {
        long answer = 0;
        
        long min=0; //최솟값
        
        Arrays.sort(times); 
        ////n과 times 모두 int형이므로 계산할 때 long형으로 바꿔줘야함.
        long max = (long) n*times[times.length-1]; //최악의 경우 -> 시간이 가장 오래 걸릴 때.
        
        while(min<=max){
            
            long half = (max+min)/2; //모든 사람이 검사받는 예상 시간
            //System.out.println("("+min+","+max+") "+answer);
            
            //총 몇 명 처리하는지도 long형으로 해야함.max일 때 인원이 엄청 많을 수 있음.
            long total=0; //시간이 half라면 총 몇 명 처리할 수 있는지.
            for(int i=0;i<times.length;i++)
                total+=half/times[i]; //시간이 answer 만큼 지났을 때 검사받은 사람 수
            
            if(total<n) //n명 다 처리 못함 -> 시간 더 필요
                min = half+1;
            else{ //n명 이상 처리->시간 조금 줄여보기
                answer=half; //n명을 처리할 수 있는 최소한의 시간이니 answer값 저장해두기.
                max = half-1;
            }
        }
        
        return answer;
    }
}