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

   해당 문제의 원문은 여기서 확인하자.

문제 이해

   각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다르며 처음에 모든 심사대는 비어있는 상태이다. 한 심사대에서는 동시에 한 명만 심사할 수 있으며 입국심사를 위해 줄을 서있는 n명 중 가장 앞에 서 있는 사람이 비어 있는 심사대로 가서 심사 받을 수 있다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있다. 이때 모든 사람이 심사를 받는데 걸리는 최소 시간을 구하는 문제이다.

   입국심사를 기다리는 사람 수 n이 주어지고, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 주어진다. 제한 사항은 다음과 같다.

 

• 1 ≤ n ≤ 1,000,000,000
• 1 ≤ 심사 시간 ≤ 1,000,000,000 (분 단위)
• 1 ≤ 심사관 수 ≤ 100,000

---

접근 방식

   이분 탐색의 개념을 이용해 문제를 해결하였다. 이분 탐색의 대상은 걸리는 시간으로 0분부터 최대 시간(심사시간이 가장 긴 심사관이 n명의 사람을 전부 심사하는 시간)으로 잡아주었다. 구한 범위를 이용해 특정 시간동안 모든 심사관들이 처리 가능한 인원 수를 구해 최소 n명을 만족하는지 확인하는 과정을 거치며 범위를 줄여나가면 된다.

   예제를 살펴보자. 입국심사를 기다리는 사람은 10명이며 각 심사관들의 심사 시간은 배열로 주어져있다.

 

   최소 심사 시간을 구하기 위해 우선적으로 이분 탐색의 범위를 설정해주어야 한다. min값은 0, max값은 최악의 경우를 고려해야 하기 때문에 8 * 10인 80으로 초기화한다. (min도 더 세부적으로 구할 수 있지만 간단하게 0으로 초기화하였다.)

 

 

   이제 구해진 범위에서 이분 탐색을 통해 임의로 걸리는 시간을 하나씩 뽑게 된다. 처음 값은 0 ~ 80의 중간값인 40으로 해당 값에 대해 각 심사관들이 심사할 수 있는 사람의 총합을 구한다.

   심사 가능한 사람의 총합이 137명으로 필요 인원인 10명을 가볍게 넘어선다. 심사 시간이 너무 길기 때문에 max 값을 줄여준다.

 

 

   범위는 0 ~ 39로 줄게 되었으며 중간값인 19에 대해 심사 가능한 인원을 구해보자. 이번에도 가능한 인원 수를 훌쩍 넘는 것을 확인할 수 있다.

 

 

   이번 범위는 0 ~ 18이며 중간값은 9이다. 아직도 심사 가능한 인원의 수가 훨씬 많다. 더 줄여보자.

 

 

   범위는 0 ~ 8이며 중간값은 4이다. 이번엔 심사 가능한 인원의 수가 11명으로 많이 줄어들었다. 하지만 아직도 10명보다 많은 상태이기 때문에 max값을 줄이게 된다.

 

 

   범위는 0 ~ 3이며 중간값은 1이다. 이번엔 가능한 인원이 2명으로 너무 줄어버렸다. 이번엔 min 값을 증가시켜보자.

 

 

   범위는 2 ~ 3이며 중간값은 2이다. 인원이 5명으로 부족하다. min 값을 다시 증가시킨다.

 

 

   범위는 3 ~ 3이며 중간값은 3이다. 인원이 8명으로 아직도 부족하다. min 값을 다시 증가시킨다.

 

 

   범위는 4 ~ 3이 되며 min 값이 max 값을 넘어서게 되었다. 이 시점에서 이분 탐색이 종료되며 min 값을 반환한다. 이전 과정에서 4분의 시간에서 심사 가능한 총 인원의 수는 11임을 확인하였다. 따라서 최소 심사 시간은 4분이 된다.

---

코드

public class 프로그래머43238번 {
    public long solution(int n, int[] times) {
        long min = 0;
        long max = 0;

        for (int t : times)
            max = Math.max(max, t);
        //걸리는 최대 시간은 심사시간이 가장 오래걸리는 심사관이 n명을 전부 심사하는 경우
        max *= n;
        while (min <= max) {
            long mid = (min + max) / 2;
            long pass = 0;
            //각 심사관들이 시간 안에 심사할 수 있는 사람의 수의 총합
            for (int t : times)
                pass += mid / t;
            if (pass < n) min = mid + 1;
            else max = mid - 1;
        }
        return min;
    }
}