프로그래머스_입국심사(C++)

 

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

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

[문제 풀이]

이분탐색을 이용하여 문제를 풀었습니다.

이 문제는 n명의 사람이 입국 심사를 모두 마치는 데 걸리는 최소시간을 구하는 문제입니다. n과 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 = 0;
    long long maxTime = times[times.size() - 1] * (long long)n;
    
    long long answer = maxTime;
    
    while(minTime <= maxTime){
        
        long long midTime = (minTime + maxTime) / 2;
        long long done = 0;
        
        for(int item : times)
            done += midTime/item;
        
        if(done < n){
             minTime = midTime + 1;

        }
        else {
            if(midTime <= answer)
                answer = midTime;
            maxTime = midTime - 1;
        }
    }
    
    return answer;
}