[프로그래머스] Level 3. 입국 심사

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

프로그래머스

 

 

실패한 방법 (시간초과)

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>

using namespace std;

long long solution(int n, vector<int> times) {
    
    auto compare = [](pair<int, long long>& a, pair<int, long long>& b){ 
        if(a.second != b.second) return a.second > b.second;
        else return a.first > b.first;
    };
    
    priority_queue<pair<int, long long >, vector<pair<int, long long>> , decltype(compare)> pq(compare);
    vector<long long> finTs(n,0);
    
    for(int i=0; i<times.size(); i++){
        pq.push(make_pair(i,times[i]));
    }
    
    while(n>0){
        auto p = pq.top();
        pq.pop();
        
        finTs[p.first] += times[p.first]; //끝나는시간갱신.      
        pq.push(make_pair(p.first, p.second + times[p.first]));
     
        n--;
    }
    
    auto it =  max_element(finTs.begin(),finTs.end());
    return *it;
}

 

이 방법은, pq에서 매번 최소 종료시간을 찾아야하기 때문에 시간이 오래걸린다(O(NlogM) 

이진탐색(Binary Serach) 를 이용하면 제한 시간 안에 문제를 풀 수 있다. 

 

 

해결 방법

1. 가장 적게 걸리는시간 low = 1, 가장 오래 걸리는 시간 max = (최대심사칸)*n으로 설정한다.
2. mid  를 low 와 max의 중간으로 설정하고, 해당 시간동안 n명을 처리할 수 있는지 검사한다.
3. 만약 처리할 수 있다면 max = mid-1 로, 처리할 수 없다면 low = mid+1 로 변경하여 범위를 좁힌다.
4. 범위를 좁혀가며 나오는 유효한 mid의 최솟값을 찾는다.

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

long long solution(int n, vector<int> times) {
    long long left = 1; // 최소 시간
    long long right = (long long) *max_element(times.begin(), times.end()) * n; // 최대 시간
    long long answer = right;

    while (left <= right) {
        long long mid = (left + right) / 2; // 중간 시간
        long long count = 0;

        // mid 시간 동안 심사대에서 몇 명을 처리할 수 있는지 계산
        for (int time : times) {
            count += mid / time;
            if (count >= n) break; // 이미 n명을 넘었으면 더 확인할 필요 없음
        }

        if (count >= n) {
            answer = mid; // n명 이상을 처리할 수 있으면 최적값 갱신
            right = mid - 1; // 시간을 더 줄일 수 있는지 확인
        } else {
            left = mid + 1; // 시간이 부족하면 더 늘려야 함
        }
    }

    return answer;
}

 

 

절반가르기 전략이다. 

내가만들었던 알고리즘은 실패했지만, pq에서 원하는 함수로 세팅하는것을 배웠다.

   auto compare = [](pair<int, long long>& a, pair<int, long long>& b){ 
        if(a.second != b.second) return a.second > b.second;
        else return a.first > b.first;
    };
    
    priority_queue<pair<int, long long >, vector<pair<int, long long>> , decltype(compare)> pq(compare);

 

a.second 가 b.second보다 작을 경우 pq의 앞에 와야하는데, pq는 기본적으로  max-heap이기 때문에 true를 반환하는것이 우선순위가 낮다는 의미이다. 그래서 부호를 거꾸로 적어야 의도한 대로 나온다.