코딩 테스트 - 입국심사

입국심사

문제 링크 : 입국심사

문제 설명

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

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

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

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

제한 사항

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

입출력 예

n	times	return
6	[7, 10]	28

풀이 방법

• 제한 사항을 보면 n의 최대 값은 1,000,000,000이고, times 배열의 길이 최대 값은 100,000이다. 이는 n을 하나씩 검사하면서 올라가면 무조건 시간초과가 나는 문제다. n을 기준으로 했을 때, O(logN) 이하의 시간복잡도를 가지게끔 해야 한다.
• 처음에는 우선순위큐를 사용해서 times의 값들을 천천히 늘려가면서 총합을 n까지 가볼까 했다가 그 방법은 예상하건데 무조건 시간초과가 날 것 같았다.
• O(logN)의 시간복잡도를 가지는 알고리즘에는 분할 탐색을 떠올렸고, 이를 응용해서 문제를 해결하고자 했다. 최악의 경우, 즉 가장 크게 나올 수 있는 값은 times에서 가장 큰 값을 n으로 곱한 값이고, 가장 작은 값은 0이라고 가정을 하고, 중간 값을 times의 값들로 나눈 합이 n과 크거나 같아지는 경우 정답에 도달할 것이라고 생각했다. 그리고 주의할 점은 times에는 같은 값이 들어있을 수도 있고, n과 같아지더라도 그 범위가 넓을 수 있기 때문에 n과 크거나 같은 경우더라도 범위가 1이 될 때까지 실행해야 된다는 점이다.
  -> 해당 문제 풀이는 O(logN * M)의 시간복잡도가 걸릴 것이고, N은 최대 1,000,000,000, M은 최대 100,000이기 때문에 알맞은 알고리즘으로 보인다.

구현

#include <string>
#include <vector>

using namespace std;

long long solution(int n, vector<int> times) {
    long long answer = 0;
    
    sort(times.begin(), times.end());
    
    long long left = 0;
    long long right = (long long)times.back() * n;
    
    while(left <= right){
        long long mid = (left + right) / 2;
        
        long long sum = 0;
        for(int i : times){
            sum += mid / i;
        }
        
        if (sum < n){
            left = mid + 1;
        }else {
            answer = mid;
            right = mid - 1;
        }
    }
    
    return answer;
}