입국심사

문제정의

---

입국 심사관들이 승객들을 심사하는데 걸리는 가장 최소 시간을 구하는 문제이다. 문제 링크

문제풀이

---

import java.util.*;

public class Immigration {

    //프로그래머스 문제풀이 level3 입국심사
    public static void main(String[] args) {
        int n = 6;
        int[] times = {7, 10};

        Arrays.sort(times);
        System.out.println(BinarySearch(times, n, times[times.length-1]));
    }
    public static long BinarySearch(int[] times, int n, long max)
    {
        long l = 1, r = max * n;
        long mid = 0;
        long ans = Long.MAX_VALUE;
        while(l < r)
        {
            mid = (l+r)/2;
            if(isPassed(times, n, mid))
            {
                ans = Math.min(ans, mid);
                r = mid-1;
            }
            else
                l = mid+1;
        }
        return ans;
    }

    public static boolean isPassed(int[] times, int n, long mid)
    {
        int amount = 0;

        for(int i = 0; i < times.length; i++)
            amount +=  mid / times[i];

        if(amount >= n)
            return true;
        return false;
            
    }
    
}

전체 코드는 다음과 같다.

일단 심사하는데 걸리는 시간을 정렬한다. 이 문제를 해결하기 위한 큰 그림은 이분탐색을 활용하는 것이다. 이분탐색의 mid를 걸리는 최대 시간으로 가정한다. 그리고 이 최대시간을 적용했을 때 모든 승객들을 심사할 수 있는지 검사한다. 만약 모든 승객을 검사할 수 있다면 midr값을 줄이고, 아니라면 mid값을 늘린다.

이분 탐색에서 초기 l값은 1로 r값은 가장 오래 걸리는 심사기간에 n을 곱한다. 그 뒤로는 isPassed함수를 통해 모든 승객을 심할 수 있는지 검사하고 만약 검사할 수 있다면, 정답을 더 작은 쪽으로 업데이트하고 r값을 mid+1로 업데이트한다.

그렇지 않다면 mid값이 더 커져야 한다는 의미이므로 l을 mid+1로 업데이트한다.

isPassed를 검사하는 방법은 들어온 mid값에 대해 심사위원의 시간을 나눠서 검사를 할 수 있는 사람의 수를 전부 더해본다. 만약 이 값이 n을 넘는다면, true를 반환하고, 그렇지 않으면 false를 반환한다.

times의 길이를 m이라 하고, times에서 가장 큰 값을 x라 한다면, 최종 시간복잡도는 \[O(mlognx)\]이다.

테스트

처음 풀이를 틀려서 다른 사람의 풀이를 참고했는데, 이게 전형적인 이분탐색 문제라고 해서 알아보지 못한 내 자신이 원망스러웠다. 학교 수업 때 이러한 유형을 풀어본 적이 있기 때문이다. 보통 엄청 큰 수가 나오고 최소 또는 최대를 구하라는 문제가 이분탐색의 유형에 해당된다고 한다. 앞으로는 잘 기억해두어야 겠다.