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

접근 방식

문제에서 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 구하라고 합니다.

어떻게 최솟값을 구할 수 있을까요?

 

모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 구하기 위해선 제일 시간이 적게 걸리는 심사대에 가장 많은 인원을 심사받게 해주면 됩니다. 왜냐하면 제일 시간이 적게 걸리는 심사대에 최대한 많은 인원을 배치해야 회전률이 더 빠르기 때문입니다.

 

접근 방식 증명

 

주어진 예제로 설명해보겠습니다.

 

 

맨 처음(0분)에 2명이 심사를 받으러갑니다.

7분뒤에 왼쪽 심사가 종료가 되고, 한명이 심사를 받으러 갑니다.

현재 누적된 시간은 7분이고, 심사를 완료한 인원은 1명입니다.

 

10분뒤에 오른쪽 심사가 종료되고, 한명이 심사를 받으러 갑니다.

현재 누적된 시간은 10분이고, 심사를 완료한 인원은 2명입니다.

 

14분후 왼쪽 심사가 종료되고, 한명이 심사를 받으러 갑니다.

 

현재 누적된 시간은 14분이고, 심사를 완료한 인원은 3명입니다.

 

20분후, 오른쪽 심사가 종료됩니다. 하지만, 심사를 받으러 가지 않습니다.

1분만 더 기다린 후 왼쪽 심사를 받는 것이 더 빠르기 때문입니다.

제일 시간이 적게 걸리는 심사대에 가장 많은 인원을 심사를 받도록 해줍니다.

현재 누적된 시간은 20분이고, 심사를 완료한 인원은 4명입니다.

 

21분후, 왼쪽 심사도 종료가 되고, 왼쪽 심사를 받으러 갑니다.

현재 누적된 시간은 21분이고, 심사를 완료한 인원은 5명입니다.

 

28분에 모든 심사가 종료됩니다.

모든 인원을 심사하는데 걸린 시간은 28분이 됩니다.

예제 문제의 정답인 28과 동일한 결과가 나옵니다.

 

알고리즘

어떤 알고리즘을 사용해서 풀까요?

 

단순 선형 탐색은 시간복잡도가 너무 커서 불가능합니다.

모든 사람이 입국 심사를 통과해야 하는 최소 시간을 찾아야 하니, 시간 복잡도가 O(logN)인 이분 탐색 알고리즘을 사용합니다.

 

 

풀이 코드

import java.util.*;

class Solution {

    public long solution(int n, int[] times) {
        long answer = 0;
        long start = 1;
        long end = 100_000L * 1_000_000_00;
        
        Arrays.sort(times);
        
        while(start <= end) { 
            long mid = (start + end) / 2;
            
            if(check(mid, times, n)) { // 크기 감소
                answer = mid;
                end = mid - 1;
            }else {
                start = mid + 1;
            }
        }

        return answer;
    }
        
    boolean check(long checkTime, int[] times, int n) { // O(n) = 100,000
        long cnt = 0;
        long cntTime = 0;
        
        for(int time: times) {
            cnt += checkTime / (long) time;
            
            if(cnt >= n) {
                return true;
            }
        }
        
        return false;
    }
}

 

최소 시간과 최대 시간을 각각 지정하고, 이분 탐색으로 범위를 줄여가면서 최소를 만족하는 값을 찾습니다.

이 로직에서 핵심은 check메서드 입니다.

boolean check(long checkTime, int[] times, int n) { // O(n) = 100,000
        long cnt = 0;
        long cntTime = 0;
        
        for(int time: times) {
            cnt += checkTime / (long) time;
            
            if(cnt >= n) {
                return true;
            }
        }
        
        return false;
    }

 

최솟값을 찾아야 하므로, cnt >= n인 경우, 즉 주어진 시간 내에 심사가 가능한 인원이 심사해야 하는 인원보다 같거나 많다면, 더 적은 시간으로도 모든 사람이 입국 심사를 받을 수 있다는 가능성이 있습니다. 따라서 시간을 줄여서 더 최적의 값을 탐색할 수 있습니다

 

 

시간 복잡도

 

O(NlogN)

배열 정렬 + 이분 탐색시 탐색한 값에대해 확인하는 과정

 (단, N은 풀이 코드의 변수와는 관계가 없습니다.)

 

출력 결과