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

미숙한 블로그 주인이 코딩테스트 문제를 풀어가는 과정을 담은 글입니다. 이 풀이가 효율적인 풀이가 아닐 수 있으며, 부정확한 정보가 많이 있을 수 있습니다. 보완해야할 점이 있다면 댓글로 남겨주세요!

 

https://programmers.co.kr/learn/courses/30/lessons/43238

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

입국심사

문제

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

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

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

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

제한사항

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

 

풀이

입출력 예시

 

풀이

입국 심사에 걸리는 시간은 최악의 경우, 심사에 가장 오래 걸리는 심사관 x n이다. 이 값을 high로, 0을 low로 해서 이분탐색을 진행해 답을 구해야한다.

 

low와 high의 값이 바뀌는 기준을 지정해줘야한다. 이 기준은, low와 high의 중앙값인 mid를 times 배열에 있는 수로 나눈 몫을 더한값 count로 지정했다. 이것의 의미는, 중앙값 mid의 시간동안 각 심사관이 처리할 수 있는 사람의 수를 더한 것이다. 이 값을 기준으로 low와 high를 변환시켜 나가면 된다.

#include <vector>
#include <algorithm>

using namespace std;

long long solution(int n, vector<int> times) {
    long long high;
    long long low = 0;
    long long mid;

    high = (long long)*max_element(times.begin(), times.end());
    high *= n;
    
    while (true) {
        if (high == low) {
            return high;
        }
        mid = (high + low) / 2;
        
        long long count = 0;
        for (int i = 0; i < times.size(); i++) {
            count += mid / times[i];
        }

        if (count >= n) {
            high = mid;
        }
        else {
            low = mid + 1;
        }
    }
}