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

문제 설명

입국 심사관이 사람이면 반드시 심사관에 따라 속도는 다를 것 입니다.

여러분이 입국한 날이 첫 출근인 심사관과 오늘부로 20년 근속을 찍은 심사관까지 다양하겠죠.

첫 출근인 심사관은 긴장해서 입국 심사가 늦어지고, (신입 심사관이라고 하겠습니다.)

20년 근속 심사관은 신참 보다는 속도가 분명 더 빠를 것입니다. (경력 심사관이라고 하겠습니다.)

경력 심사관의 능력이 너무 뛰어나 신입 심사관이 1명을 전담하는 동안 2명 이상의 입국자를 심사할 수 있습니다.

이제 입국 심사를 받아야할 차례가 다가오고 있습니다. 여러분은 어느 심사관에게 가고 싶나요?

아마, 여행의 설렘에 얼른 공항을 나가고 싶어 경력 심사관을 더 선호 하겠죠!

하지만 중요한 것은 빨리 심사를 받아 나가는 것

이미 길게 늘어선 경력 심사관 대기 줄 끝에 당신이 대기한다면 신입 심사관의 대기는 0명으로

오히려 시간이 더욱 걸릴 수 있습니다.

이 문제를 풀 때는 항상 빨리 나가고 싶다는 마음을 갖고 풀어보면 이해하기 쉽습니다.

문제에서 주어진 범위에서 모든 경우의 수를 계산할 경우, 주어진 시간 내 해결하지 못하는 실패한 알고리즘이 됩니다.

따라서, 이분 탐색을 이용해 최소 시간을 구해보겠습니다.

먼저, 이분 탐색에서 사용할 범위는 최소 시간 0 부터 최악의 시간 (신입 심사관의 시간 * 전체 인원) 까지

범위를 설정합니다.

그리고 비교 방법은 최소부터 최악 사이 중간 값에서 현재 모든 심사대의 사간을 나누어

처리량(인원)이 부족하면 (중간 값, 최악의 시간) 범위에서 재탐색을 실행하고

처리량(인원)이 남으면 (최소의 시간, 중간 값) 범위에서 재탐색을 실행합니다.

이때, 각 심사대는 병렬처리로 진행되므로 동시에 실행된다는 점을 주의해야 합니다.

위의 과정을 코드로 표현하면 다음과 같습니다.

long long solution(int n, vector<int> times) {

    // 최소 시간 : 대기자가 0명인 경우
    unsigned long long left = 0;    
    
    // 이분 탐색을 위한 중간 값 변수
    unsigned long long mid;         
    
    // 최악의 시간 : N명 모두가 가장 오래 걸리는 심사관에게 받고자 함.
    unsigned long long right = (*std::max_element(times.begin(), times.end())) * n;
    
    // 현재 주어진 시간에서 최대한 처리할 수 있는 총 인원 수
    unsigned long long total;
    
    while(left < right)
    {
        mid = (left + right) / 2;
        total = 0;
        
        // 각 심사관이 최대한 처리할 수 있는 사람들을 모두 더하자.
        for(int t : times)
        {
            // t 심사관이 최대한으로 처리할 수 있는 사람
            // (각각의 심사관은 독립적이다!)
            total += (mid / t); 
        }
        
        // 최대한 처리했을 때, 처리량(total)이 인원수(n) 보다 많을 경우
        if(total >= n)
            right = mid;
        // 최대한 처리했을 때, 처리량(total)이 인원수(n) 보다 부족한 경우
        else
            left = mid + 1;
    }
    
    return left;
}

추가

만약, 재귀 함수로 구현할 경우 오버플로우가 발생할 수 있으니

가능하면 반복문으로 구현하는 것이 좋습니다.

출처

입국 심사