코딩 테스트 연습-이분탐색-입국심사

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

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

본문에 앞서 해당 문제는 다른 분들의 솔루션을 참고하고 풀었음을 밝힙니다.

 

본 문제는 문제가 속한 카테고리를 보면 알 수 있듯이 이분탐색 기법을 사용하여 해결할 수 있는 문제입니다.

 

이분탐색 기법을 사용하여 문제를 풀라고 힌트를 주었지만, 이분탐색 기법을 어떻게 적용해야할지 도저히 감을 잡을 수 없었습니다. 다른 분들의 솔루션을 곰곰히 읽어보니 이분탐색에 대한 이해도가 낮았음을 깨달을 수 있었습니다.

 

먼저, 이분탐색을 통해 문제를 해결하기위해서는 우리가 구하고자하는 문제의 정답(최적해)이 특정 범위안에 존재함을 가정할 수 있어야합니다.

 

우리는 해당 문제에 대하여 이 특정 범위를 제한할 수 있습니다.

 

우선, 해가 존재할 수 있는 범위의 상한값 t_max  를  검사하는데 가장 오랜 시간이 걸리는 심사관이 모든 사람들을 검사하는데 걸리는 시간으로 제한하였습니다. 그러면 우선 정답 t 의 범위가 (t <= t_max)  로 제한됨을 알 수 있습니다. 그런데, 이진 탐색 방법을 사용하려면 t 가 될 수 있는 값의 범위의 하한값을 정의해주어야 합니다. 저는 하한값 t_min 을 검사하는데 가장 적은 시간이 걸리는 심사관이 한 사람을 검사하는데 걸리는 시간으로 제한하였습니다.

 

범위를 제한하는 과정이 끝났다면 이분탐색 기법을 사용하여 해를 찾아주면 됩니다. 그런데, 해를 탐색하기 위해서 어떠한 해가 우리 문제의 해인지를 판단할 수 있어야합니다. 먼저, 입국심사하는데 M 시간이 소요됐다면, 검사하는데 K 시간이 걸리는 한 심사관이 M 시간 동안 검사한 사람의 수 T 는 floor(M/K )로 정의될 수 있습니다. 각 심사관 별로 M 시간 동안 검사한 사람의 수를 모두 합한 수가 N 보다 크거나 같다면 탐색 범위의 상한값을 M-1 로 정의 후 다시 탐색하고, N 보다 작다면 탐색 범위의 상한값을 M+1 로 정의 후 다시 탐색하다보면 최적해를 찾을 수 있습니다.

 

저는 심사관 별로 M 시간 동안 검사한 사람의 수를 모두 합한 수가 N 과 같을때, 이분탐색 기법을 수행하기 위해 사용되는 반복문을 바로 탈출하도록 코드를 구현하여 삽질을 좀 했습니다... 생각해보니 심사관 별로 m(<M) 시간 동안 검사한 사람의 수를 모두 합한 수가 N 인 경우가 존재함을 깨닫고 알고리즘을 수정하여 맞출 수 있었습니다.

 

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

using namespace std;

long long solution(int n, vector<int> times) {

    sort(times.begin(), times.end());
    
    long long min_time = (long long)times[0];
    long long max_time = (long long)times[times.size() - 1] * n;
    long long answer = max_time;
    
    while(min_time <= max_time)
    {
        long long mid = (min_time + max_time)/2;
        long long sum = 0;
        
        for(int time:times)
            sum += mid/time;
        
        if(sum >= n) // 해당 시간안에 심사 가능한 사람수가 n 보다 많거나 같다면
        {
            answer = min(answer, mid); 
            max_time = mid-1;   
        }
        else // 해당 시간안에 심사 가능한 사람수가 n 보다 적다면
        {
            min_time = mid+1;
        }
    }
    
    return answer;
}