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

문제 링크

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

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

 

문제 요약

n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.

 

처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.

모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.

 

입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.

 

입력

입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.

각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.

심사관은 1명 이상 100,000명 이하입니다.

 

출력

모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.

 

접근법

처음 문제를 봤을 때는 Lv.3 문제 치고 매우 쉬운 문제같다고 느꼈다.

각 심사대에서 입국심사가 끝나는 시간을 계속 업데이트(해당 입국심사대에서 걸리는 시간을 누적) 하면서 PriorityQueue에 집어넣는다. n명의 입국심사를 할 때까지 PriorityQueue에서 poll() 하면서, 맨 마지막에 poll()한 입국심사대의 심사가 끝나는 시간이 n명의 입국심사가 끝나는 최소 시간이 된다.

그런데 이렇게 구현했더니 테스트 케이스 1번 ~ 4번만 맞고 5번 ~ 8번은 시간초과가 떴다.

 

잘 생각해보니 입국심사를 기다리는 사람이 최대 1,000,000,000명이고, 심사관이 100,000명이므로

한 명의 입국심사를 할 때마다 PriorityQueue에서 poll()과 add()를 각각 한번씩 해야 한다.
PriorityQueue에서 poll() 할 때마다 O(logN), add() 할 때마다 O(logN) (여기서 N은 최대 100,000)
log2(100,000)은 약 16이므로 한 번의 입국심사에 32 + a의 연산이 필요하다.

입국심사를 기다리는 사람이 최대 1,000,000,000명이므로
worst case에서 최소 32,000,000,000의 연산을 요구하므로 시간초과가 날 수밖에 없다. 

 

따라서 이 문제는 PriorityQueue로 단순 구현하라는 문제가 아니다. 물론 약간의 트릭? 사전 연산?을 하면 PriorityQueue로 구현할 수 있다. 이는 아래쪽에서 다시 설명하겠다.

 

아무튼 이 문제는 프로그래머스의 문제 분류에 나와있는 것 처럼 이분탐색을 이용해서 제한 시간 내로 풀 수 있다.

바로 n명이 심사를 받는데 걸리는 시간의 최솟값을 이분탐색으로 찾는 것이다. 

1. n명이 심사를 받는데 걸리는 시간의 최댓값을 대략적으로 구한다. 나는 가장 빠른 입국심사대에서 n명이 전부 입국심사를 받는 경우 걸리는 시간(min(times) * n)을 최댓값으로 정했다. 이 값을 maxTime이라고 하자.
2.  minTime(초깃값은 0) ~ maxTime 사이의 값에서 이분 탐색을 시작한다. 이분탐색에서는 mid 값을 사용해야 하므로 여기서는 midTime이라고 한다. midTime = (minTime + maxTime) / 2 이다.
3. 이분탐색을 하며 midTime 값이 갱신될 때마다, midTime 안에 n명이 전부 입국심사를 받을 수 있는지 체크한다.
4. 만약 midTime 시간 안에 n명 이상이 입국심사를 받을 수 있다면, midTime을 답으로 저장해두고 maxTime = midTime - 1 로 갱신한다. 만약 midTime 안에 n명이 입국심사를 전부 받지 못한다면, minTime = midTime + 1로 갱신한다.
5. 이분탐색이 끝나면, 저장해둔 답을 반환한다.

*참고: 위 알고리즘에서 minTime과 maxTime의 초깃값은 매우 대충 정한 값이다. 하지만 일단 min(times) * n의 최댓값이 1,000,000,000,000,000,000으로 long 범위 이내이고, 이분탐색 알고리즘의 시간 복잡도는 O(logN)이므로 log2(1,000,000,000,000,000,000) = 약 60 정도이다. 따라서 이렇게 말도 안되는 큰 값이어도 시간 내로 문제를 충분히 풀 수 있다.

 

위 알고리즘이 PriorityQueue로 단순 구현한 것보다 잘 동작하는 이유는, 이분탐색의 시간 복잡도는 O(logN)으로 아주 빠르고, midTime 안에 n명 이상이 입국심사를 받을 수 있는지 확인하는 부분의 시간복잡도는 O(N)이기 때문이다. 여기서 N은 최대 100,000(심사관 수) 이므로, worst case에서 60 * 100,000 = 6,000,000의 연산 안에 답을 구할 수 있다. n이 너무 큰 것이 PriorityQueue 접근법의 문제였는데, 이 문제에서는 이 n의 영향을 이분탐색으로 상쇄시켜버렸다.

 

이 문제에서 주의할 점이 있다면, 이분탐색의 세부 조건이 일반적인 이분탐색과 다르다는 것이다. 먼저 주어진 시간 내에 몇명이 입국심사를 받을 수 있는지 확인하는 코드를 보면

long countImmigrationInTime(long limitTime, int[] times)
{
    long cnt = 0;
    for (int time : times)
        cnt += limitTime / time;
        
    return cnt;
}

나머지를 고려하지 않은 나누기 연산을 사용하기 때문에 다음과 같은 경우가 생길 수 있다.

 

int[] times = {7, 10}이고, limitTime = 29일 때
29 / 7 = 4, 29 / 10 = 2
따라서 cnt = 6

int[] times = {7, 10}이고, limitTime = 28일 때
28 / 7 = 4, 28 / 10 = 2
역시 cnt = 6

 

예제의 경우에서 답은 28인데, 딱 6명을 입국심사 할 수 있는 29를 찾는 순간 이분탐색을 종료해버리면 오답이 된다는 것이다. 이 것을 고려하면서 이분탐색을 구현해야한다. 자세한 내용은 전체 코드를 확인하면 이해할 수 있을 것이다.

 

 

*약간의 사전 연산을 통해 PrioirtyQueue만으로 문제를 푸는 법

구글링을 통해 발견한 아이디어이다. 매우 재밌는 방식을 썼다.

 

각 심사관이 1분에 몇 번의 입국심사를 할 수 있는지 구한다 (1 / (한 명 입국심사하는데 걸리는 시간)) 그리고 그 값을 전부 더한다.

 

전부 더한 그 값이 의미하는 것은, 모든 입국심사관이 쉬지 않고 계속 입국심사를 했을 때, 1분동안 입국심사를 받을 수 있는 사람의 숫자가 된다.

 

그리고 n을 이 값으로 나눈 값을 x라고 했을 때, x는 모든 입국심사관들이 x분 일했을 때 n명을 전부 심사할 수 있다는 것을 의미한다.

물론 엄밀히 말하면 틀렸다. 왜냐면 이 값은 각 입국심사관의 업무 효율을 누적해서 계산한 값이기 때문이다. 즉 k명의 입국심사관을 융합시켜서 한명으로 만들면, x분만 일하면 입국심사를 전부 끝낼 수 있다는 것이다.

 

하지만 이 x의 값을 다음과 같은 의미로 해석할 수 있다. "모든 입국심사관이 적어도 x분 정도는 일해야 n명의 입국심사가 전부 끝난다"

 

따라서 이 값을 이용해서, PriorityQueue를 초기화할 때 각 입국심사관이 x분동안 입국심사를 진행했다는 가정 하에 초기화를 한다. 이러면 n의 값을 충분히 줄인 채로 실제 알고리즘이 동작하기 때문에 시간 내로 문제를 풀 수 있다.

 

자세한 건 코드로 남겨두겠다.

 

 

시간 복잡도

위 설명에 있다.

 

 

공간 복잡도

이분탐색의 경우 추가적인 메모리가 필요하지 않다.

 

 

풀면서 놓쳤던 점

이분 탐색의 구현 조건. 이분 탐색 구현은 쉬웠지만, 언제 break를 해야하는지, 답은 어떻게 저장해야하는지 등의 디테일한 부분은 까다로웠다.

 

 

이 문제에서 얻어갈 점

이분 탐색의 응용. 다양한 최적화 아이디어.

 

 

코드

 

이분탐색 버전

import java.util.*;

class Solution {
    public long solution(int n, int[] times) {
        
        long minTime = 0;
        long leftTime, rightTime, midTime;
        
        leftTime = 0;
        rightTime = getLimitTime(n, times);
        midTime = (leftTime + rightTime) / 2;
        
        while (leftTime <= rightTime)
        {
            midTime = (leftTime + rightTime) / 2;
            
            long immigrationCnt = countImmigrationInTime(midTime, times);
            
            if (immigrationCnt >= n)
            {
                minTime = midTime;
                rightTime = midTime - 1;
            }
            else if (immigrationCnt < n)
                leftTime = midTime + 1;
        }
        
        return minTime;
    }
    
    long countImmigrationInTime(long limitTime, int[] times)
    {
        long cnt = 0;
        for (int time : times)
            cnt += limitTime / time;
        
        return cnt;
    }
    
    long getLimitTime(int n, int[] times)
    {
        long minTime = Integer.MAX_VALUE;
        for (int time : times)
            minTime = Math.min(minTime, time);
        
        return minTime * n;
    }
    
}

 

PriorityQueue 버전

import java.util.*;

class Solution {
    public long solution(int n, int[] times) {
        
        PriorityQueue<Immigration> immigrationPQ = new PriorityQueue<>();
        
        double immigrationPerMin = 0;
        for (int time : times)
            immigrationPerMin += 1D / time;
        
        double averageWorkload = n / immigrationPerMin;
        
        long estimatedImmigrationCnt;
        for (int time : times)
        {
            estimatedImmigrationCnt = (long)(averageWorkload / time);
            immigrationPQ.offer(new Immigration(time, time * (estimatedImmigrationCnt + 1)));
            n -= estimatedImmigrationCnt;
        }
        
        Immigration immigration;
        long endImmigrationTime = (long)averageWorkload;
       for (int person = 1; person <= n; person++)
        {
            immigration = immigrationPQ.poll();
            
            endImmigrationTime = immigration.endTime;
            immigration.endTime += immigration.immigrationTime;
            immigrationPQ.add(immigration);
        }
        
        return endImmigrationTime;
    }
    
}

class Immigration implements Comparable<Immigration>
{
    int immigrationTime;
    long endTime;
    
    Immigration (int immigrationTime, long endTime)
    {
        this.immigrationTime = immigrationTime;
        this.endTime = endTime;
    }
    
    public int compareTo(Immigration o)
    {
    	return Long.compare(this.endTime, o.endTime);
    }
}