입국 심사

핵심 아이디어

데이터 범위가 굉장히 크기 때문에 이진 탐색을 생각해 봐야 한다. 문제에서는 '모든 사람이 심사를 받는데 걸리는 시간의 최솟값'을 요구 했으니 '시간'을 기준으로 범위를 잡자.

심사위원의 처리 시간을 고민해 보면, 먼저 가장 짧게 걸릴 수 있는 시간은 얼마일까? 사람이 한명 들어온다 했을 경우, 1분만에 심사를 하는 심사위원이 있는 것이다. 반대로 가장 길게 걸리는 시간은 ''심사위원 중 심사를 가장 느리게 하는 심사 위원에게 모든 사람이 몰리는' 경우이다. -> 처리를 가장 느리게 하는 심사위원의 속도 * n명의 사람들.

이를 통해, 최소 시간과 최대 시간을 확인했다. 해당 값들을 이용해서 이분 탐색을 진행한다. 최솟값과 최댓값을 절반으로 나누고 해당 값이 동일한지, 작은지, 큰지를 판단하자. 

• 해당 문제의 핵심은 데이터가 엄청나게 많기 때문에 C++ 같이 데이터 타입이 있는 형태의 언어는 int 대신 long long을 사용해야 함을 잊지 말자! 

코드 구현

C++

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

long long solution(int n, vector<int> times) {
    long long answer = 0;
    // 이진 탐색을 사용하기 위해서 시간을 정렬 한다.
    sort(times.begin(), times.end());
    
    // 최솟값은 즉 가장 적게 걸리는 시간은 1분
    long long min = 1;
    // 가장 오래 걸리는 시간은: 가장 오래 걸리는 심사위원 시간 * n 명
    long long max = n * (long long)times.back();
    
    /* 이분 탐색 시작 */
    while (min <= max){ // 최댓값과 최솟값이 바뀌면 가장 최소 시간이다.
        long long mid = (max + min) / 2;
        long long temp = 0; // 처리할 수 있는 명 수를 넣는다.
        // 현재 시간 기준으로 심사위원들이 
        // 몇명을 처리하는지 확인하는 부분
        for (int i = 0; i < times.size(); i++){
            temp += (mid / (long long) times[i]);
        }
        // 현재 값 보다 많은 사람을 처리할 수 있는 경우 -> 최대 시간을 줄인다.
        if (temp >= n){
            max = mid - 1;
            answer = mid;
        }
        // 현재 값보다 적은 사람을 처리할 수 있는 경우 -> 최소시간 늘려야한다.
        else min = mid + 1;
        
    }
    return answer;
}

 

예를들어, 최솟값 1분 최댓값 60분을 기준으로 이진 탐색을 진행한다고 가정해보자. 값을 반으로 나눴을 때, 해당 값에 심사위원들이 처리할 수 있는 사람의 수를 구한다. 7분 걸리는 심사위원은 4명, 10분 심사위원은 3명 처리할 수있다. 이때, 최소 시간으로 모든 사람을 처리해야 하기 때문에 시간을 더 줄일 수 있다. 

더 줄이기 위해서 이전의 이진 탐색의 결과를 다시 최댓값으로 두고 이어서 이분 탐색을 진행한다. 따라서 최대 시간과 최소 시간이 바뀔때까지 진행하면 입국심사의 최소기간을 구할 수 있다. 

for (int i = 0; i < times.size(); i++){
    temp += (mid / (long long) times[i])
   }

 

현재 인원 보다 더 많은 사람들 처리할 수 있는 경우 -> 시간을 더 줄일 수 있다.

if (temp >=n){
    // 최대 시간을 줄인다.
    max = mid - 1;
    answer = mid;
}

 

현재 인원보다 적은 사람들 처리할 수 있는 경우

else min = mid + 1;