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

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

문제링크: 입국심사

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

 

문제 설명

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

입출력 예 설명

가장 첫 두 사람은 바로 심사를 받으러 갑니다.

7분이 되었을 때, 첫 번째 심사대가 비고 3번째 사람이 심사를 받습니다.

10분이 되었을 때, 두 번째 심사대가 비고 4번째 사람이 심사를 받습니다.

14분이 되었을 때, 첫 번째 심사대가 비고 5번째 사람이 심사를 받습니다.

20분이 되었을 때, 두 번째 심사대가 비지만 6번째 사람이 그곳에서 심사를 받지 않고 1분을 더 기다린 후에 첫 번째 심사대에서 심사를 받으면 28분에 모든 사람의 심사가 끝납니다.

 

---

풀이과정

물론 문제 유형에도 이분 탐색이라고 적혀있지만, 추후 실제 이러한 문제가 어떠한 테스트에 나왔을 때를 생각하여 입력 값의 범위를 먼저 봐야한다. 입국심사를 기다리는 사람이 1,000,000,000명 이하고, 심사하는데 최대 시간도 1,000,000,000분 이하, 심사관도 100,000명 이하이기 때문에 범위과 굉장히 넓다. 그러므로 이진탐색을 한번 생각을 해봐야 한다. 이진 탐색에 대한 개념은 여기 에서 한번 확인하고, 차근차근히 한번 생각해보자.

1. 이진 탐색으로 접근하게 되면 어떤 값을 기준으로 범위를 좁혀 나가면서 답을 찾아내야 할지 생각한다.
2. 문제에서는 모든 사람이 심사를 받는데 걸리는 시간의 최솟값 을 요구 했으니 시간 을 기준으로 범위를 잡아본다.
3. start는 가장 최솟값이므로, 기다리는 사람 수가 1이고 심사 시간이 1분만 걸리는 심사관 밖에 없을 때를 생각해본다면 1이 나온다.
4. end 역시 시간을 기준으로 생각했을 때, 심사 시간이 가장 오래 걸리는 사람에게 n명 모두 갔을 때이다. => times[times.size()-1] * n
5. start와 end 범위를 잡았으니 이진 탐색을 시작한다.
6. 좀 헷갈렸던 부분이 cnt 라는 변수 인데, 이 cnt 는 시간이 아닌 mid 시간동안 심사 처리할 수 있는 모든 사람 수를 의미한다.
7. 그래야 이 cnt 값으로 최소 시간을 찾을 수 있기 때문이다.
8. 그래서 cnt(mid 시간 동안 심사 처리할 수 있는 모든 사람 수) 가 기존 n(기다리는 사람 수) 보다 작으면 해당 문제 조건을 만족하지 못하기 때문에 최솟값인 start 를 mid +1로 갱신해서 다시 탐색을 한다.
9. 그리고 cnt가 만약 n명 이상을 충족했을 때는, end 값을 다시 갱신해준다 (end = mid - 1)
10. 9번 조건을 만족했을 때, 탐색하는 기준 시간(mid)이 최대값(end) 보다 작으면 문제 조건을 충족하기 때문에 mid 값이 최소 시간이 될 수 있다는 의미다. 따라서 answer에 계속 갱신해준다.
11. 이를 while 문의 조건인 start <= end 일 때까지 계속 반복하다보면 모든 사람이 심사를 받는데 걸리는 시간의 최솟값이 나온다.

 

코드

#include <vector>
#include <vector>

// n = 기다리는 사람 수
// times = 심사하는데 걸리는 시간
// times.size() = 심사관수
long long solution(int n, vector<int> times) {
    long long answer = 0;
    // 가장 오래 걸리는 심사관의 시간을 알기 위한 정렬
    sort(times.begin(), times.end());

    // 시간으로 기준을 두었을 때 최소 => n이 1이고, 심사 시간이 1분만 걸리는 심사관 밖에 없을 때
    long long start = 1;
    // 시간으로 기준 두었을 때 최대 => 심사 시간이 가장 오래 걸리는 사람에게 n명 모두 갔을 때
    long long end = (long long) times[times.size()-1] * n;
    // 탐색 범위(시간) 기준
    long long mid;

    while(start <= end) {
        // 중앙값
        mid = (start + end) / 2;
        // mid 시간동안 심사 처리할 수 있는 모든 사람 수
        long long cnt = 0;

        for(int i = 0; i < times.size(); i++) {
            // 각 시간별 mid 시간 동안 처리할 수 있는 사람들 수를 더해준다.
            cnt += mid / times[i];
        }

        // mid 시간동안 처리할 수 있는 모든 사람 수가 n명 보다 작기 때문에 해당 문제 조건 만족 X
        if(cnt < n) {
            // 최소값을 mid + 1 로 좁혀준다.
            start = mid + 1;
        }
        // mid 시간 동안 처리할 수 있는 사람들이 n명 이상으로 해당 문제의 조건을 만족한다면
        else {
            // mid(기준 시간) 값이 end(최대 시간) 값 보다 이하면
            // mid 는 최소값이 될 수도 있기 때문에 answer에 넣어주고
            if(mid <= end) {
                answer = mid;
            }
            // 최소 값을 찾기 위해 범위를 더 좁혀준다
            end = mid - 1;
        }
    }

    return answer;
}