[프로그래머스] [C++] 입국심사*** (binary search)

1. 문제

심사하는 직원들은 각각 심사하는데 시간이 전부 다르다

 

이 시간들의 배열이 주어지고

 

입국 심사해야하는 사람의 수 n이 주어진다.

 

이때 모든 사람을 심사했을때 걸리는 최소의 시간을 구하여라.

 

 

2. 큐를 활용한 풀이 =>  시간 초과

이는 그리디 적으로 풀 수 있다.

모든 사람이 가장 빨리 끝나는 심사 위원을 선택만 하기만하면된다.

 

따라서 모든 시간을 우선순위 큐에 넣어놓고

 

n번을 그리디적으로 선택 하는 것이다.

 

그 후 가장 긴 시간을 찾으면 된다.

 

이는 nlogn 으로 입력이 아주 큰 문제이므로 시간초과가 나오게 된다.

#include <string>
#include <vector>
#include <algorithm>
#include <queue>
 
using namespace std;
 
long long solution(int n, vector<int> times) {
    long long totalTime = -1;
    priority_queue<pair<long long, int> > pq;
    for(int i = 0; i < times.size(); i++)
        pq.push(make_pair(-(long long)times[i], i));
    for(int i = 0; i < n; i++)
    {
        pq.push(make_pair(pq.top().first-times[pq.top().second], pq.top().second));
        pq.pop();
    }
    for(int i = 0; i < times.size(); i++)
    {
        totalTime = max(totalTime, -pq.top().first - times[pq.top().second]);
        pq.pop();
    }
    return totalTime;
}

#include <string>
#include <vector>
#include <algorithm>
#include <set>
 
using namespace std;
 
long long solution(int n, vector<int> times) {
    long long totalTime = -1;
    multiset<pair<long long, int> > pq;
    for(int i = 0; i < times.size(); i++)
        pq.insert(make_pair(times[i], i));
    for(int i = 0; i < n; i++)
    {
        pq.insert(make_pair(pq.begin()->first + times[pq.begin()->second], pq.begin()->second));
        pq.erase(pq.begin());
    }
    for(auto it = pq.begin(); it != pq.end(); it++)
        totalTime = max(totalTime, it->first -times[it->second]);
    return totalTime;
}

 

3. 이분 검색

(-1, max time) 구간안에서 이분 탐색을 하면 답을 얻어 낼 수 있다.

 

이때 이분 검색의 결과 값은 lo < x <= hi 가 된다.  

 

기본적인 이분 검색 알고리즘에서 mid 값에 대한 함수를 따로 작성하면된다.

 

이 함수는 복잡하지 않으므로 따로 작성하지는 않았다.

 

이 함수는 총 mid 시간을 가질때 가능한 최대 인원 수 를 구하는 것이다.

 

이 결과값에 대하여 이분 검색을 lo + 1 ==  hi 이 될 때 까지 수행하면

 

답이 나온다.

 

#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
long long bSearch(long long n, long long lo, long long hi, vector<int>& times) {
    if(lo + 1 == hi) {
        return hi;
    }
 
    long long mid = (lo + hi)/2;
    long long sum = 0;
 
    for(auto& time : times) {
        sum += mid/time;
    }
    if(sum < n) {
        return bSearch(n, mid, hi, times);
    }
    else {
        return bSearch(n, lo, mid, times);
    }
}
 
long long solution(int n, vector<int> times) {
    return bSearch(n, -1, (long long)*max_element(times.begin(), times.end()) * n + 1, times);
}