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

프로그래머스 level3 입국심사

 

소요시간 : 아마도 ... 2시간30분...?3시간...????

 

너무 어려웠다..

기초 아이디어를 다른 사람에게 듣고 코드 짰다....

통과가 왜 안되는 지 잘모르겠고 통과가 왜 되는 건지도 잘 모르겠다

코드 조금만 바꿔도 안되는데 이해가 안간다.

 

어쨌든 푼 방법은

제일 많이 걸리는 시간을 max 로 한 후에

이분탐색으로 처리할 수 있는 사람보다 많으면 right 를 줄이고 적으면 left를 올려서

시간을 구하는 것이다.

이 때 찾고 있는 시간을 찾더라도 더 작은 시간이 있는 경우 때문에 right 를 -1해서 더 검색해본다.

 

import java.util.Arrays;

class Solution {
    public long solution(int n, int[] times) {
    	Arrays.sort(times);
    	long left = 0;
    	long N = n;
    	long right = times[times.length-1] * N;
    	long mid = 0;
    	long min = Long.MAX_VALUE;
    	while(true) {
    		if(left > right) break;
    		mid = (left + right) / 2;
    		
    		long count = 0;
    		for (int i = 0; i < times.length; i++) {
				count += mid / times[i];
			}
    		
    		if(count < N) left = mid+1;
    		else {
    			right = mid-1;
    			min = mid;
    		}
    	}
    	return min;
    }
    
}