[Programmers] 입국심사 - 이분탐색(Binary Search)

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

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

 

접근

우선 문제의 접근법부터 생각해야 한다. 이 문제를 이분탐색으로 풀게 된 이유는 문제의 범위를 보면 간단히 알 수 있다. 입국 심사를 기다리는 사람이 최대 1,000,000,000 명, 한 명을 심사하는 데 걸리는 시간이 최대 1,000,000,000 분이므로 O(n) 의 시간복잡도 마저 부담스러운 값이 나온다. 이러한 매우 큰 범위가 주어지면, O(logn) 의 시간복잡도를 가지는 이분탐색을 우선적으로 고려해야 한다.

이후에 생각해야 할 것은 무엇을 기준으로 이분탐색을 할 것인가를 생각해야 한다. 정답인 answer 가 시간의 최솟값을 요구하였으므로 시간을 기준으로 이분탐색을 진행하면 된다는 생각을 할 수 있다. 이제 진행해보자.

 

풀이

• 최소값 : 가장 적은 시간이 걸리는 경우의 수는 손님이 단 1 명 존재하고, 이 사람이 심사를 받는 데 걸리는 시간이 1  분 걸리는 경우이다. (minTime = 1)
• 최대값 : 가장 오랜 시간이 걸리는 경우의 수는 손님 n 명이 모두 심사하는데 가장 오래 걸리는 심사관에게 심사를 받는 경우이다. (maxTime = n * times[times.size() - 1], times 는 정렬된 상태여야 한다.)
• 추가로 내가 찾으려는 특정 시간에 심사할 수 있는 사람 수의 최대값을 구해야 한다. 이 값이 n 보다 크거나 같을 때 해당 시간은 문제의 조건을 만족하고, 이 시간들 중 최소값이 정답이 된다.

 

코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

long long solution(int n, vector<int> times) {
    sort(times.begin(), times.end());
    long long minTime = 1;
    long long maxTime = (long long)times[times.size() - 1] * n;
    long long avgTime;
    long long answer = 0;
    
    while(minTime <= maxTime){
        avgTime = (minTime + maxTime) / 2;
        
        long long cnt = 0;
        for(int time : times){
            cnt += avgTime / time;
        }
        
        if(cnt < n) minTime = avgTime + 1;
        else maxTime = avgTime - 1;
    }
    
    return minTime;
}