입국심사

문제

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

코드

import java.util.*;

class Solution {

    private int is_prom(int n, long mid, int[] times){
        long left_man = n;
        for(int time : times){
            left_man -= (mid/time);
        }
        // System.out.println("n : " + n  + ", left_man : " + left_man);
        if(left_man > 0)
            return -1;
        else
            return 0;
    }


    public long solution(int n, int[] times) {
        long answer = 0;
        long low = 0;
        long high = 0;
        for(int i=0; i<times.length; i++)
            high = Math.max(high, times[i]);
        high *= n;
        high += 10;
        answer = high;
        while(low <= high){
            long mid = (low+high)/2;
            // System.out.println("answer : " + answer + ", mid : " + mid);
            int res = is_prom(n,mid,times);
            if(res == -1){
                low =  mid + 1;
            }else if(res == 0){
                // System.out.println("answer updated : " + answer + " -> " + mid);
                answer = Math.min(answer, mid);
                high = mid - 1;
            }
        }


        return answer;
    }
}

피드백

• 첨 봤을땐 이게 어케 이분탐색이야? 생각했다.
  • 근데 일단 최적해의 범위가 long의 범위라 O(N log N)도 안될 것이니 이분탐색 밖에 없다고 생각이 들었다.
• 결론부터 말하자면 최적해를 이분 탐색으로 찾을 수 있다.
  • 이분탐색을 하고 그 것이 답 인지 확인하고 그 이후 범위를 바꾸면 된다.
• 답을 찾는 과정은 다음과 같다.
  • mid 동안 각 심사관이 몇 명을 심사할 수 있는지 계산한다.
  • n명 이상 처리할 수 있으면 시간이 넘치니까 high를 줄인다.
  • n명 미만 처리 가능하면 시간이 부족하니 low를 높인다.