Today's Algorithm(2019-01-24)

programmers. 입국심사

이분탐색 문제의 유형이 비슷해서 이 문제를 접근하는데 크게 어렵지 않았습니다. 물론 아마 프로그래머스 내 이분탐색 부류에 있지 않았다면 이렇게 접근하는데 좀 더 시간이 걸렸을지도 모르겠네요. 기본적인 해법은 mid값일 때 얼마만큼의 사람이 통과되었는지를 구하고 이를 바탕으로 low와 high를 조절하는 것입니다.

 

그런데 이 문제를 풀면서 가장 어려웠던 것은 type이 int가 아닐수도 있다는 점입니다. 즉, 다시 말하면 최악의 상황의 경우 문제에서는 int가 주어졌지만 int가 넘어가는 값이 최악의 상황(=high)이 될 수가 있다는 것입니다. 예를들어 심사관 1명 밖에 없고 1명을 검사하는데 1,000,000,000분이 필요한데 1,000,000,000명이 기다리고 있는 상황이 그럴 수 있죠. 그렇기 때문에 long 타입으로 계산을 하고 마지막엔 int 캐스팅을 통해 제출하면 됩니다(캐스팅 안하면 오류가 발생합니다!)

 

class Solution {
    public int solution(int n, int[] times) {
        int max = 0;
        for (int time : times) {
            if(time > max) max = time;
        }

        long low = 1;
        long high = (long)max * n;  // 최악의 상황

        while (low + 1 < high) {
            long mid = (low + high) / 2;
            long count = passCount(mid, times);
            if (count < n) low = mid;
            else high = mid;
        }

        if(passCount(low, times) >= n) return (int)low;
        return (int)high;
    }


    public long passCount(long mid, int[] times) {
        long count = 0;
        for (int time : times) {
            if (time > mid) continue;
            count += (mid / time);
        }
        return count;
    }
}