프로그래머스. 디스크컨트롤러(c++) / 힙(Heap)

[메인로직]

현재 시간(sec)이하의 요청 시간을 가지고 있는 작업들을 모두 최소 힙에 넣고 => 힙에 pair<작업시간, 요청시간> 형태로 저장했다.

그 중 가장 작은 작업 시간을 가지는 작업을 수행한다.

위의 로직을 모든 작업이 끝날때까지 반복하면 된다!

 

하지만!!!!! [[0 , 3], [4, 4], [5, 3], [4, 1]] 이 테스트케이스에서 오류가 발생했다.....

작업을 수행하면서 현재 시간을 sec += (작업의 소요시간) 으로 더해주었는데,,,,,,

위 케이스에서는 첫 번째 작업 수행 후, sec = 3이 되면 3이하의 요청시간을 가지는 작업이 하~~~나도 없기 때문에 의미없이 while문을 계속돌아서 TimeLimit이 발생한다.

따라서, 위와 같이 priority_queue에 아무것도 없을 경우에는 현재시간 sec를 다음 요청시간인 sec = 4로 갱신시켜주어야 한다!

 

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
 
using namespace std;
 
bool check[501];
int N = 0;
 
bool isAllDone(){
    for(int i=0; i<N; i++){
        if(check[i]==false){
            return false;
        }
    }
    
    return true;
}
 
 
int solution(vector<vector<int>> jobs) {
    int answer = 0;
    
    sort(jobs.begin(), jobs.end());
    
    int currentTime = jobs[0][0]+jobs[0][1];
    answer += jobs[0][1];
    check[0] = true;
    int currentIdx = 0;
    N = jobs.size();
    
    while(!isAllDone()){
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        
        for(int i=0; i<N; i++){
            if(check[i]==true) continue;
            if(currentTime>=jobs[i][0]){
                pq.push(make_pair(jobs[i][1], jobs[i][0]));
            }
        }
        
        if(pq.empty()){
            currentTime = jobs[currentIdx+1][0];
            continue;
        }
        
        int requestTime = pq.top().second;
        int runningTime = pq.top().first;
        pq.pop();
        answer += (currentTime+runningTime-requestTime);
        currentTime += runningTime;
        
        for(int i=0; i<N; i++){
            if(jobs[i][0]==requestTime && jobs[i][1]==runningTime){
                check[i] = true;
                currentIdx = i;
            }
        }
    }
    
    answer /= jobs.size();
    
    return answer;
}