myBlog

문제 설명 보기

>> programmers.co.kr/learn/courses/30/lessons/43238

해당 문제의 핵심은 이것을 이분탐색법을 사용해 해결할 생각을 하는것이다.

문제가 설명한대로 실제 구현을 하게 되면 무조건 time out을 맞게 되어있다.

문제가 원하는 반환값은 시간이며, 시간은 항상 오름차순으로 정렬되어있다고 볼 수 있다.

이분탐색의 핵심인 정렬되어있는 숫자에서 탐색하는 범위를 절반으로 줄여 나가는 방법으로 O(logN)의 시간복잡도로 해결 할 수 있다.

> Solution

class Solution {
    public long solution(int n, int[] times){
        long left = 1;
        long right = (long)1000000000 * (long)1000000000;
        long mid = 0;
        long answer = 1;
        long sum;

        while( right > left ){
            mid = (left + right) / 2;
            sum = 0;
            for(int num : times){
                sum += mid / num;
            }
            if(sum >= n){
                answer = mid;
                right = mid;
            } else if (sum < n){
                left = mid + 1;
            }
        }

        return answer;
    }
}

* right는 입국 심사를 기다리는 10억명이 한명을 심사하는데 10억 분 걸리는 심사관 혼자서 심사하는 경우인, 가질 수 있는 가장 큰 숫자를 지정했다. Long.MAX_VALUE - 1을 사용해보았으나 아무래도 12번째 line에서 overflow가 발생하는 듯 싶어 이와같이 수정하였다.