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

안녕하세요! 코딩하는 경제학도 쏘코입니다.

오늘은 새로운 이분탐색이라는 주제의 문제를 풀어봤습니다.

이분탐색은 겉보기에는 아주 기초적인 내용같은데, 실제로 아이디어를 떠올리기는 굉장히 어려운 알고리즘중 하나입니다.

그래도 떠올리기만 하면 구현은 그렇게 어렵지 않은 편이긴 합니다!

바로 문제로 넘어가시죠!

출처 : 프로그래머스 코딩테스트 연습 고득점 KIT, programmers.co.kr/learn/courses/30/lessons/43238

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

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

programmers.co.kr

0. 문제 설명

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

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

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

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

0.0. 제한사항

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

0.1. 입출력 예

n	times	return
6	[7, 10]	28

0.2. 입출력 예 설명

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

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

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

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

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

1. 풀이 과정

나올 수 있는 최소 시간과 최대 시간을 정해두고, 그 사이에서 정해진 시간에 처리할 수 있는 사람의 수를 계산해 가면서 n명의 사람을 처리할 수 있는 최소한의 시간을 구하는 식으로 구할 수 있습니다.

최소 시간과 최대 시간 사이에서 특정 시간을 골라서 찾아야 하는데, 이 때 사용하는 것이 이분탐색입니다.

최소 시간과 최대 시간을 더해서 2로 나누면 평균 시간이 나오는데, 이 값은 우리가 찾으려는 범위의 중간값이 됩니다. 이렇게 가운데를 뚝 잘라서 두개로 나눠서 찾기 때문에 이분탐색이라는 이름이 붙은 것이죠.

먼저 min_time, max_time, mid_time 변수를 만들고, 특정 시간에 처리할 수 있는 사람 수를 저장할 변수인 sum_n을 만듭니다. min_time은 1로 설정하고, max_time은 times 벡터에서 가장 빠르게 심사하는 시간을 n만큼 곱한 값으로 초기화해줍니다. 이것은 times라는 심사시간이 주어졌을 때, n명의 사람이 가장 빠르게 심사하는 사람에게 심사받는다고 생각하는 것입니다. 만약에 여기서 times에 값이 늘어나면(심사관의 수가 늘어나면) 그만큼 시간이 단축될 수 있기 때문에 이렇게 설정합니다. (times 벡터에서 가장 느리게 심사하는 시간을 n만큼 곱한 값으로 초기화할 수도 있지만, 가장 빠르게 심사하는 시간을 n으로 곱한 값에 비해 평균탐색시간이 더 걸리게 됩니다. 1부터 100까지중에 하나를 찾는 것이 1부터 200까지중에 하나를 찾는 것보다 더 빠르겠죠? 즉 같은 탐색이라면 시간이 덜 걸리는 것이 좋겠죠?!)

특히, 모든 변수를 long long형태로 지정해야 합니다. 제한사항을 보면 10억명 이하의 사람이 대기중이며, 심사관 1명당 심사시간이 최대 10억분까지 걸릴 수 있고, 심사관은 10만명 이하라고 했습니다. 일반 int값으로는 약 21억이 넘어가면 더이상 계산을 할 수 없습니다. 만약 우연히 10억분이 걸린다면 max_time을 계산할 때 10억*3만 해도 21억이 넘어가므로 정상적인 곱셈이 되지 않기 때문에, 모든 변수를 long long 형태로 바꾸고, 곱셈할 때도 int * int 형태로 곱셈이 되어서 int형 결과값이 나오지 않도록 둘 중 하나를 long long으로 형변환을 시켜줍니다.

이제 아래 while문을 하나 만들어줍니다. while문은 min_time이 max_time보다 커지는 경우 멈추게 됩니다.

mid_time을 계산해서 할당하고, sum_n은 0으로 초기화해줍니다.

for문을 돌려서 mid_time을 times[i]로 나눈 값을 sum_n에 계속해서 더해줍니다. 이건 모든 심사원들이 mid_time이라는 시간 안에 처리할 수 있는 사람의 수를 더한 값이 됩니다. 모든 사람의 한계치를 더하면 sum_n이 되는 것이죠.

이제 if문을 만듭니다. sum_n이 n보다 크거나 같으면 더 많은 사람을 처리할 수 있다는 이야기가 되므로 max_time을 mid_time-1로 바꿔줍니다. 그리고 answer에 mid_time을 할당합니다.

여기서 왜 >가 아닌 >=를 사용했냐면, 계산 과정에서 sum_n = n을 거치지 않고 answer를 구할 수도 있기 때문입니다.

아래 주석으로 자세히 적었지만, 간단하게 설명하면 0보다 더 크고 2보다 더 작은 수는 1뿐입니다. 이렇게 굳이 1을 찾을 때 1을 검색하지 않아도 알 수 있는 경우가 발생하기 때문에, sum_n이 n보다 크거나 같은 경우에 answer를 할당합니다.

반대로 sum_n이 n보다 작은 경우에는 min_time에 mid_time+1을 할당합니다.

이렇게 반복해서 while문을 벗어나게 되면, 최종적으로 answer를 반환합니다.

2. 소스 코드

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

using namespace std;

/*
    시간 복잡도: O(n)
    공간 복잡도: O(n)
    사용한 알고리즘: DFS(깊이 우선 탐색)
    사용한 자료구조: vector, 재귀
    
    논리 :
    mintime과 maxtime을 설정해놓고 중간값인 midtime을 설정한 후에, 그 값을 times[i]로 나눈 값들을 sum_n에 더해준다.
    sum_n은 midtime이라는 시간에 처리할 수 있는 사람의 수를 뜻한다.
    sum_n이 n보다 크면 maxtime을 mid_time-1로 줄이고,
    sum_n이 n보다 작으면 mintime을 mid_time+1로 늘린 후에 다시 while문을 돌린다.
    sum_n과 n이 같아지는 순간의 mid_time이 return값이 된다.
*/
long long solution(int n, vector<int> times) {
    long long answer = 0;
    // 최소시간을 1로 설정
    long long min_time = 1;
    // 최대 시간은 times에서 가장 빠르게 심사하는 사람 * n (두 사람이 넘어가면 나눠서 맡으면 적어도 이것보다는 빠르게 처리가 가능하니까)
    // 주의! int * int이므로 값이 int로 한정되지 않게 하나 이상을 long long으로 변환해야 한다.
    long long max_time = (long long)*min_element(times.begin(), times.end()) * n;
    // mid_time은 min_time과 max_time의 중간값, sum_n은 mid_time/times[i]의 합
    long long mid_time;
    long long sum_n;
    
    while (min_time <= max_time){ // min_time이 max_time보다 커지면 종료
        mid_time = (min_time+max_time) / 2;
        sum_n = 0;
        for (int i = 0; i < times.size(); ++i) // 모든 심사원들이 mid_time에 처리할 수 있는 사람의 수를 sum_n에 담는다
            sum_n += mid_time/times[i];
        if (sum_n >= n){ // sum_n이 n보다 크면
            max_time = mid_time-1; // max_time은 mid_time-1 (왼쪽에 답이 있음)
            answer = mid_time;
            // sum_n을 구할 때 mid_time을 사용했으므로, 반드시 mid_time을 answer에 넣어야 한다.
            // min_time이나 max_time을 넣으면 안되는 이유는, sum_n을 구할 때 사용한 값이 min_time, max_time이 아니기 때문이기도 하고
            // 테스트케이스 3, [1,2,3], 2 와 1, [2,2], 2 를 넣어보면 더 확실하게 알 수 있다.
            // sum_n > n, sum_n < n, sum_n = n 케이스로 나눠서 할 수도 있는데, 이 경우에도 sum_n = n일 때만 answer에 값을 할당하면 안된다
            // 계산 과정에서 sum_n = n을 거치지 않고 answer를 구할 수도 있기 때문이다
            // 위 테스트 케이스에서 1, [2,2], 2가 바로 그 케이스이다. times가 같은 경우 sum_n = n을 거치지 않고 sum_n > n으로 바로 넘어갈 수도 있기 때문이다.
        }
        else // sum_n이 n보다 작으면
            min_time = mid_time+1; // min_time은 mid_time+1 (오른쪽에 답이 있음)
    }
    
    // while문을 빠져나오면 
    return answer;
}