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

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

프로그래머스

문제 풀이

이분탐색 문제라고 나와있지만 막상 문제를 접하면 어떤 값을 탐색해야 할지 감을 잡기 힘들다. 구글링 해보니 전체 시간 범위를 지정하여 이분탐색 하고 해당 시간으로 n명에게 입국심사를 진행할 수 있는지 비교해나간다.

따라서 전체 시간의 범위는 0부터 가장 대기시간이 긴 시간*n명이 되므로 해당 범위를 이분탐색을 진행한다.

 

값의 범위 10억으로 곱셈을 하다보면 int의 범위를 금방 벗어나기 때문에 long으로 선언해준다.

코드

import java.util.Arrays;

class Solution {
    public long solution(int n, int[] times) {
        long answer = 0;
        long left=0;
        long right = times[times.length - 1] * (long)n;
        Arrays.sort(times);
        while (left <= right) {
            long mid = (left + right) / 2;

            long cnt = 0;
            for (int t : times) {
                cnt += mid / t;
            }

            if (cnt<n)
                left = mid + 1;
            else{
                right = mid - 1;
                answer = mid;
            }
        }

        return answer;
    }
}

 

이 부분이 가장 애먹었던 부분이다.

times도 n도 int기 때문에 long = int * int였다. 당연한 논리 오류지만 막상 코딩할 때 자주 지나치고 디버깅 할 때 찾게 된다

long right = times[times.length - 1] * (long)n;