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

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

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

 

문제 요약

 n명의 사람들이 입국심사를 기다리고 있다. 각 입국심사관의 입국심사 시간은 times 배열에 주어진다. 모든 사람이 심사받는 최소 시간을 반환해야 한다.

 

문제 풀이

 이 문제의 핵심은 시간(mid)이 주어지면 그 시간 동안 몇명까지 통과시킬 수 있는지 확인할 수 있다는 것이다. 이를 통해 mid를 앞 뒤로 움직이며 이분 탐색으로 문제를 풀어낼 수 있다.

 

 우선 left를 최소 시간인 1, right를 최대 시간인 (가장 늦은 심사원 * 대기자)로 초기화 후 시작한다. 이분 탐색을 위해 mid값을 구한 후 mid분 동안 몇명의 고객을 대응할 수 있는지를 n과 비교한다. n보다 적은 손님만을 대응할 수 있다면 left를 mid + 1로 초기화하며, n보다 같거나 많은 손님을 대응할 수 있는 경우에는 answer과 비교하여 최저값을 찾고 right를 mid - 1로 초기화하여 다시 탐색한다.

 

 이 문제와 거의 동일한 문제를 모 회사 코딩테스트에서 만난 적이 있다. 그 당시에는 이분탐색으로 풀어야 겠다는 생각조차 못했었던 문제였다. 이 문제를 풀면서 이분탐색에 대한 확실한 이해가 생겼으며 다시 이분탐색 문제를 만나더라도 해결할 수 있는 능력이 생긴 것 같다.

 

나의 코드

import java.util.Arrays;

class 입국심사 {
    public long solution(int n, int[] times) {
        Arrays.sort(times); //  이분 탐색을 위한 정렬

        /* 이분 탐색 */
        long left = 1; // 최소 시간
        long right = (long)times[times.length - 1] * n; // 최대 시간
        long answer = right;
        long mid, amount;
        while (left <= right) {
            mid = (left + right) / 2;
            amount = 0;
            for (int t : times)
                amount += mid / t;

            if (amount >= n) {
                answer = Math.min(answer, mid);
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return answer;
    }
}