[Heap, 난이도 중상] 프로그래머즈, 디스크 컨트롤러

본인이 짠 소스 코드의 전체적인 처리 과정은 이렇다.

1. 작업 길이가 짧은 작업을 우선으로 하는 우선순위 큐에 모든 작업들을 push한다.

2. 우선 순위 큐의 top은 가장 작업 길이가 짧은 작업인데, 현재 시간을 기준으로 아직 디스크에 들어오지 않은 작업이라면 당장 실행할 수 없으므로 임시 저장벡터에 빼둔다. 당장 실행할 수 있는 작업이 나올 때 까지 반복해준다. 

3-1. 당장 실행할 수 없는 작업이 하나도 없을 수도 있다. 이 때는 앞으로 제일 먼저 들어오는 작업들중 작업 길이가 짧은 작업을 실행해주면 된다. 현재 시간은 이 작업이 끝나는 시간으로 바꿔주면 된다.

3-2. 당장 실행할 수 있는 작업이 있다면 우선 순위 큐의 top에 해당하는 작업을 수행해주고, 현재 시간은 3-1과 마찬가지로 이 작업이 끝나는 시간으로 바꿔준다. 

4. 작업을 수행시켰다면 작업 수행 순으로 모아둔 벡터에 바로 넣어줘야 나중에 평균 대기 시간을 계산을 할 수 있다.

(본인은 작업 수행 순으로 모아둔 벡터에 (디스크에 들어온 시각, 이 작업이 끝난 시각) 데이터가 들어있는 구조체 형태로 넣어주었다. 이러면 이 작업의 최종 대기시간을 [최종 대기시간 = 이 작업이 끝난 시각 - 디스크에 들어온 시각] 으로 쉽게 계산할 수 있다.)

5. 임시 저장벡터에 저장해둔 작업이 있다면 모두 우선순위 큐에 다시 push 해준다.

 

우선순위 큐에 아무 작업도 남아있지 않을 때까지 2~5번을 반복해주면 문제가 해결된다.

  

테스트케이스 20개 모두 통과

 

#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
struct node{
    int start;
    int length;
};
bool operator<(node a, node b){
    return a.length>b.length;
}
bool compare(node a, node b){
    if(a.start==b.start) return a.length>b.length;
    else return a.start>b.start;
}
priority_queue<node> pq;
vector<node> temp_v; //임시 저장 벡터
vector<node> schedule; //작업 진행 순으로 모아둔 벡터

int solution(vector<vector<int> > jobs) {
    int answer=0;
    int li;
    for(int i=0;i<jobs.size();i++){
        pq.push({jobs[i][0],jobs[i][1]});
    }
    int time=0;
    do{
    	//현재 시간에 아직 들어오지 않은 작업은 임시 저장 벡터로 빼둠
        while(!pq.empty() && time<pq.top().start){
            temp_v.push_back(pq.top());
            pq.pop();
        }
        //현재 실행할 작업이 하나도 없을 경우
        if(pq.empty()){
            sort(temp_v.begin(),temp_v.end(), compare);
            node nextnode=temp_v[temp_v.size()-1];
            temp_v.pop_back();
            time=nextnode.start+nextnode.length;
            schedule.push_back({nextnode.start,time});
        }
        else{
            time+=pq.top().length;
            schedule.push_back({pq.top().start,time});
            pq.pop();
        }
        //임시로 저장 했던 작업 벡터들을 다시 pq안에 넣음
        while(!temp_v.empty()){
            li = temp_v.size()-1; //last index
            pq.push({temp_v[li].start,temp_v[li].length});
            temp_v.pop_back();
        }
    }while(!pq.empty());
    for(int i=0;i<schedule.size();i++){
        answer+=(schedule[i].length-schedule[i].start);
    }
    return answer/schedule.size();
}