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

문제 설명

 

프로그래머스

 

접근 방법

해당 문제는 이분 탐색을 이용하여 해결할 수 있었습니다.

 

n명의 입국자에 대해 최대한 빨리 심사를 마치려면, 심사관 중 심사하는데 걸리는 시간이 가장 적은 사람에 가장 많은 입국자를 배정해야합니다. 이를 위해(이후 이분 탐색을 위함이기도) 우선적으로 심사 시간 배열(times)를 오름차순으로 정렬해줍니다.

 

class Solution {

    int[] times;

    public long solution(int n, int[] times) {
        this.times = times;
        Arrays.sort(times);
        
        // ...

 

입국자를 가장 우선적으로 심사 시간이 가장 적은 사람에게 배정해야하니, 가장 적은 심사 시간의 배수를 기준으로 심사되는 입국자의 수를 산출해 볼 수 있습니다. 예를 들어, 문제의 예시 처럼 심사 시간이 각각 7분, 10분이라고 주어질 때, 7분이라는 시간에 입국자 한명이 심사되고, 14분이라는 시간에는 3명(7분 간격 2명, 10분 간격 1명), 21분이라는 시간에는 5명(7분 간격 3명, 10분 간격 2명), 28이라는 시간에는 6명(7분 간격 4명, 10분 간격 2명) 등 가장 적은 심사 시간의 배수를 기준으로 심사되는 입국자의 수를 산출하면 시간별로 가장 빨리 심사되는 입국자 수의 모든 경우를 고려할 수 있게 됩니다.

 

이를 바탕으로 가장 적은 심사 시간의 배수를 presentTime 변수를 인자로 두어 아래 로직의 메서드를 호출하면 가장 빨리 심사되는 입국자의 수를 얻을 수 있습니다.

 

    private long getImmigrants(long presentTime) {
        long immigrants = 0;

        for (int time : times) {
            if (presentTime >= time) {
                immigrants += presentTime / time;
            } else {
                break;
            }
        }

        return immigrants;
    }

 

이때 배수를 일일이 1, 2, 3, 4, 5, ... 등 1씩 증가시키며, 모든 입국자를 심사(최대한 빨리)하는 경우를 구하기에는 입국자수(n)가 최대 10억이며, 심사관 중 심사하는데 가장 오래 걸리는 시간이 최대 10억이기 때문에, 시간 이슈가 발생합니다.(시간 복잡도 : O(N))

 

이때 이분 탐색을 이용하여 해당 배수를 절반씩 분할하여 탐색한다면, 순차 탐색 보다 훨씬 빠른 속도로 모든 입국자를 심사(최대한 빨리)하는 경우를 구할 수 있게 됩니다.(시간 복잡도 : O(logN))

 

        long start = 1, end = (long) times[0] * n + 1;
        while (start < end) {
            long presentTime = (start + end) / 2;
            long immigrants = getImmigrants(presentTime);

            if (immigrants >= n) {
                end = presentTime;
            } else {
                start = presentTime + 1;
            }
        }

        return end;

 

이때 Lower Bound(특정 값 n 이상인 데이터가 처음 나오는 위치)를 구하도록 했는데, 이는 주어진 심사관들로 가장 빨리 심사할 수 있는 입국자 수를 구하다보니, 정확히 n으로 일치되지 않고 n 보다 클 수도 있기 때문입니다. 하지만 이 경우도 문제에서 요구하는 사항을 충족하므로, 포함시켜주도록 합니다. 

 

나의 소스 코드

import java.util.Arrays;

class Solution {

    int[] times;

    public long solution(int n, int[] times) {
        this.times = times;
        Arrays.sort(times);

        long start = 1, end = (long) times[0] * n + 1;
        while (start < end) {
            long presentTime = (start + end) / 2;
            long immigrants = getImmigrants(presentTime);

            if (immigrants >= n) {
                end = presentTime;
            } else {
                start = presentTime + 1;
            }
        }

        return end;
    }

    private long getImmigrants(long presentTime) {
        long immigrants = 0;

        for (int time : times) {
            if (presentTime >= time) {
                immigrants += presentTime / time;
            } else {
                break;
            }
        }

        return immigrants;
    }
}

 

참고자료

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