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

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

코딩테스트 연습 - 입국심사

풀이과정

1. 이분탐색 범위 설정

입국심사에 걸리는 최소시간은 1분이고, 최대시간은 모든 입국 대기자가 가장 심사시간이 긴 심사관 1명에게 입국심사를 받는 경우(n * 최대심사시간)에 해당한다. 이 최소값과 최대값의 범위 안에서 이분탐색을 활용한다.

 

2. 임의의 시간 동안 입국심사 가능한 사람의 수 계산

심사관들의 입국심사시간이 [a_1, a_2, a_3, ... , a_k]로 주어졌을 때, 임의의 시간 t동안에 입국심사가 가능한 사람의 수 number는 다음과 같이 계산할 수 있다.

이 number가 n보다 크면 필요한 시간보다 주어진 시간이 많은 것이고, n보다 작으면 필요한 시간보다 주어진 시간이 적은 것이다.

주어진 시간이 필요한 시간보다 많을 경우 최대시간을 줄이고, 주어진 시간이 필요한 시간보다 적을 경우 최소시간을 늘려나가는 식으로 범위를 줄여나가면 된다.

 

3. n명을 심사할 수 있는 최소시간 찾기 

하지만 위의 2번의 결과에서 number == n인 t가 곧 정답은 아닌데, 이는 n명의 사람을 심사하는데 필요한 시간대 중 하나의 값이기 때문이다. 예를들어, 5분에 한 명이 심사 가능한 심사관이 1명 있을 때 5명의 입국 대기자를 심사하기 위해서는 25분 ~ 29분이 필요하다.

따라서, 위의 2번에서 number == n인 t를 찾으면 다시 number == n이 성립하는 최소 t를 찾아야 한다.

이를 위해 위의 2의 과정을 number != n 인 동안이 아니라 min < max 인 동안 돌도록 해 주면 우리가 원하는 최소 t를 찾을 수 있다.

 

소스코드

import java.util.Arrays;

class Solution {
    public long solution(int n, int[] times) {
        Arrays.sort(times);
        long minimum = 1;
        long maximum = (long) times[times.length - 1] * n;
        long mid = (minimum + maximum) / 2;

        long number = count(mid, times);
        while (minimum < maximum) {
            if (number >= n) {
                maximum = mid;
            } else {
                minimum = mid + 1;
            }
            mid = (minimum + maximum) / 2;
            number = count(mid, times);
        }

        return mid;
    }

    private long count(long t, int[] times) {
        long answer = 0;
        for (int time : times) {
            answer += (t / time);
        }
        return answer;
    }
}