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

입국심사

문제 링크

입국심사

분석

모든 심사대는 처음에 비어있습니다.

한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다.
각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.

가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사 받을 수 있습니다.

모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 구해서 반환해야합니다.

n은 입국심사를 기다리는 사람 수입니다.
times는 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열입니다.

이분탐색을 활용하는 문제입니다.

최소 시간은 1분입니다.
최대 시간은 가장 오래 걸리는 심사관의 시간 $\times n$입니다.

풀이

#include <vector>
#include <algorithm>

using namespace std;

long long solution(int n, vector<int> times) {
    long long answer = 0;
    
    // 최소 시간
    long long left = 1;
    // 최대 시간으로, 가장 느린 심사관이 모든 사람을 혼자 처리할 때 걸리는 시간
    long long right = static_cast<long long>(*max_element(times.begin(), times.end())) * n;
    
    // 이분 탐색 반복문
    while (left <= right)
    {
        // 중간값으로 현재 고려하는 시간입니다.
        long long mid = (left + right) / 2;
        // 해당 시간동안 각 심사관들이 몇 명을 처리할 수 있는지 저장한 값
        long long total = 0;
        
        // 모든 심사관이 현재 시간 동안 몇 명을 처리할 수 있는지 더한 값
        for (int time : times)
        {
            total += mid / time;
        }
        
        // 모든 사람 심사가 가능한 경우
        if (total >= n)
        {
            // 더 적은 시간으로 가능한지 왼쪽으로 탐색
            answer = mid;
            right = mid - 1;
        }
        // 시간이 부족한 경우
        else
        {
            // 시간을 늘려야하기 때문에 오른쪽으로 탐색
            left = mid + 1;
        }
    }
    
    return answer;
}

최소값과 최대값을 절반으로 나누고 해당 값이 동일한지, 작은지, 큰지를 판단합니다.

성능 요약

시간 복잡도는 $O(m \times log(n \times t))$입니다.

• 이분탐색 반복문의 횟수 $O(log_2(t \times n))$
  • t는 가장 오래 걸리는 심사관입니다.
• 모든 심사관 순회 $O(m)$
  • m은 팀사관의 수입니다.
• $O(m \times log(n \times t))$

공간 복잡도는 고정된 크기의 상수 공간을 사용하기 때문에 $O(1)$입니다.

테스트 성능

테스트 1 〉 통과 (0.01ms, 4.15MB)
테스트 2 〉 통과 (0.03ms, 4.21MB)
테스트 3 〉 통과 (0.31ms, 4.21MB)
테스트 4 〉 통과 (34.63ms, 6.85MB)
테스트 5 〉 통과 (36.89ms, 6.75MB)
테스트 6 〉 통과 (33.58ms, 6.68MB)
테스트 7 〉 통과 (43.37ms, 6.86MB)
테스트 8 〉 통과 (44.13ms, 6.85MB)
테스트 9 〉 통과 (0.01ms, 4.15MB)