[프로그래머스] (이분탐색) 입국심사(C++)

입국심사 (Level 3)

문제

전체 문제 보기

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

접근법

이 문제에서 요구하는 바는 가장 효율적인 입국심사 방식을 적용했을 때 모든 사람이 심사를 받는데 걸리는 시간의 최솟값이다. 이 문제를 풀기 위해서 두 가지 방법을 접근해볼 수 있을 것이다. 첫 번째로는 가장 효율적인 입국심사 방식의 메커니즘을 구현하는 방법이다. 방법은 의외로 간단하다. 우선순위 큐를 활용하여서, 모든 심사관들을 우선순위 큐에 "심사가 끝나는 시간을 기준"으로 삽입을 한다. 그리고 다음 사람이 왔을 때 가장 일찍 끝날 것 같은 심사관에게 심사를 받고, 심사관의 심사가 끝나는 시간을 갱신한 후 다시 우선순위 큐에 넣는다. 이를 정리하면 다음과 같다.

• 모든 사람에 대해서 (N)
  • 우선순위큐에서 첫 번째 심사관을 조회 후 pop
  • 심사관의 심사가 끝나는 시간을 갱신 후 다시 push

이 방법을 사용할 경우 원하는 값을 계산할 수는 있다. 하지만 시간 복잡도를 따져보면 이번 문제에서는 적절한 방법이 아니라는 것을 알 수 있다. 그 이유를 알기 위해서 시간복잡도를 계산해보자. 먼저 사람의 수를 \(N_p\), 심사관의 수를 \(N_e\) 이라고 했을 때 이 알고리즘의 시간 복잡도는 최악의 경우 \(O(N_p * logN_e)\)가 된다. 왜냐하면 우선순위 큐에는 항상 \(N_e\)개의 원소가 존재하고, 여기에 값을 pop, push 하게 되면 \(O(logN_e)\)만큼의 시간이 필요하기 때문이다. 해당 문제의 \(N_p\) 값이 \(1,000,000,000\) 이고, \(N_e\)값이 \(100,000\) 이기 때문에 최악의 경우 \(1,000,000,000 * log (100,000) \doteqdot 1,000,000,000 * 19.93\) 가량의 많은 시간이 요구 된다.

 

두 번째 방법으로 이분 탐색을 이용할 수 있다. 이분 탐색으로 계산을 할 때는 효율적인 입국 심사가 어떤 방식인지에 대해서는 관심이 없다. 오직 임의의 시간 \(T\)가 입국심사를 하기에 충분한 시간인지에 대한 알고리즘이 필요하고, 이 조건을 만족 할 수 있는 수많은 \(T\) 중에서 최솟값을 이분 탐색을 통해서 찾기만 하면 된다. 즉, 이 방법은 주어진 조건에서 가능한 모든 시간들을 탐색하여서 최솟값을 찾는 방법이다.

 

먼저 모든 시간을 따져야 하기 때문에 최소 시간과 최대 시간을 구해보자. 최소 시간은 1명이 가장 빠른 심사관에게 심사를 받는 경우로 1분이다. 반면 최대 시간\((T_{MAX})\)은 모든 사람(1,000,000,000명)이 가장 느린 심사관 1명에게 심사를 받는 시간(1,000,000,000 분)으로 (1,000,000,000,000,000,000 분)이다. 즉 우리는 1분 ~ 1,000,000,000,000,000,000 분 사이의 시간 중 원하는 값을 찾아야 한다. 탐색 범위가 굉장히 커 보이지만, 이를 이분 탐색으로 찾게 되면 시간 복잡도는 \(O(log(T_{MAX}))\)이고 \(log_2 (1,000,000,000,000,000,000) \doteqdot 59.79\)이기 때문에 약 60회 만에 탐색을 끝낼 수 있다.

 

그리고 1회 탐색시 임의의 시간\(mid\)이 우리가 찾는 시간인지 아닌지 구별하는 방법이 필요하다. 만약 임의의 시간 \(mid\)에서 각 심사관이 효율적으로 심사를 진행했다면 각 심사관들은 \(mid / time\) 명을 심사할 수 있을 것이다. 이 값들을 모두 더했을 때 전체 인원보다 많다면, 시간을 더 줄여도 될 것이고, 전체 인원보다 많다면 시간을 더 늘려야 할 것이다.

 

최종적으로 이분 탐색을 했을 경우 시간 복잡도는 \(O(N_e * log(T_{MAX})))\)이고 입국 심사 매커니즘을 직접구현하여 시뮬레이션할 경우 시간 복잡도는 \(O(N_p*logN_e)\)이다.  \(N_e\)값이 \(100,000\) 이고 \(N_p\) 값이 \(1,000,000,000\)이며  \(log(T_{MAX})\)와 \(logN_e\) 값이 각각 약 60, 20인 점을 고려한다면 이분 탐색으로 문제를 풀었을 때 대략 최대 \(300\)배정도 빠르다고 할 수 있다.

 

구현

#include <string>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

long long solution(int n, vector<int> times) {
    long long answer = 0;
    // 이분 탐색을 위한 left, right, mid 선언 및 초기화
    long long left = 1;
    long long right = *max_element(times.begin(), times.end()) * static_cast<long long>(n);
    long long mid = 0;

    answer = right;

    while(left <= right)
    {
        long long count = 0;
        mid = (left + right) / 2;
        // 모든 심사관이 mid 시간 내에 심사 가능한 인원수를 계산 
        for(int time : times)
        {
            count += mid / time;
        }
        // 목표보다 많은 인원을 검사할 수 있다면 시간을 줄인다.
        if ( n <= count)
        {
        // 시간을 줄일 경우 더이상 조건을 만족하는 값을 못 찾을 수 있다.
        // 그렇다면 지금의 값이 최소값이 되기 때문에 answer에 현재 시간값을 저장.
            answer = mid;
            right = mid - 1;
        }
        // 목표보다 적은 인원을 검사한다면 시간을 늘린다.
        else
        {
            left = mid + 1;
        }
    }

    return answer;
}