[lv3] 입국심사

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

 

이분 탐색 문제다. mid랑 midVal 이랑 변수명 착각해서 죙일 디버깅했다.

문제에서 최악의 경우 10억*10억의 시간이 소요되므로, 이를 end 포인터로 놓는게 핵심이다.

 

(Long.MAX_VALUE 등으로 놓으면 midVal에 오버플로가 발생함, 더 작으면 최악의 경우 케이스 틀림)

 

+ 문제엔 명시되지 않았지만, 아마 내림차순 정렬된 형태로 times가 주어지는 듯 하다.

때문에 long ed = (long) times[times.length -1] * n도 가능

class Solution {
    public long solution(int n, int[] times) {

        long answer = Long.MAX_VALUE;

        long st = 0;
        long ed = 1000000000 * 1000000000L;

        while(st <= ed) {
            long mid = st + ed >>> 1;
            long midVal = 0;

            for(int i=0; i<times.length; i++) {
                midVal += mid / times[i];
            }

            if(midVal >= n) {

                ed = mid - 1;

                if(mid < answer) {
                    answer = mid;
                }
            }
            else {
                st = mid + 1;
            }

        }
        return answer;
    }
}