[프로그래머스/Level 3] 디스크 컨트롤러 (C++)

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

코딩테스트 연습 - 디스크 컨트롤러

우선순위 큐를 이용하여 비선점 SJF 스케줄링을 구현하는 문제였습니다.

 

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
using namespace std;

int solution(vector<vector<int>> jobs) {
    int answer = 0, idx = 0, time = 0; // idx : jobs의 인덱스, time : 현재 실행시간
    // 작업 요청시간 기준 오름차순
    sort(jobs.begin(), jobs.end());
    // 작업 실행시간이 적은 순으로 선택할 최소힙
    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
    
    while(idx < jobs.size() || !pq.empty()) {
        // 지금 처리하고 있는 작업 실행시간 안에 도착한 요청이 있는 경우
        if(idx < jobs.size() && jobs[idx][0] <= time) {
            pq.push({ jobs[idx][1], jobs[idx][0] });
            idx++;
            continue;
        }
        // 힙에 처리할 작업이 남은 경우
        if(!pq.empty()) {
            time += pq.top().first; // 작업 완료 시간
            answer += time - pq.top().second; // 실제로 작업을 한 시간
            pq.pop();
        // 지금 처리하고 있는 작업 실행시간 안에 도착한 요청이 없고, heap에도 처리할 작업이 없는 경우
        } else {
            time = jobs[idx][0]; // 다음 요청이 pq에 들어갈 수 있게 시간 갱신
        }
    }
    
    return answer / jobs.size();
}