[프로그래머스] C++ 디스크 컨트롤러

문제 :

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

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

 

풀이 :

디스크 스케줄링하는 문제였다.

input으로 [[0,3], [1, 9], [2, 6]] (요청 시간, 작업 소요 시간)이 주어졌을때 

이들을 가장 짧게 작업을 끝내는 시간 / 3 하여 평균 시간을 구해주는 문제였다.

 

우선은 작업 소요 시간이 짧은 것을 먼저 처리하기 위해서 우선순위큐를 사용했다.

작업은 요청시간이 짧은 순으로 sorting 한다.

그리고 작업을 모두 돌때까지 && queue에 있는 원소를 다 처리해서 계산할때까지 반복하여 수행한다.

우선 현재시간은 작업의 소요 시간으로 누적된다.

[0,3] -> [2,6] -> [1, 9]으로 작업이 있을때 

curTime = 3 + 6 + 9 순으로 누적된다. 따라서 현재 시간 안에서 요청되는 작업이 있을 경우에 pq에 넣어준다. 

그렇게 현재 시간 안에서 요청되는 작업들을 모두 pq에 넣어놓고

pq에서 pop하며 작업 시간을 계산할 것이다.

현재 시간은 아까 말했던 것처럼 작업 시간의 누적이며

curTime += pq.top()[1]

 

answer은 현재 시간에서 중복된 요청 시간을 빼준채 누적한다.

answer += curTime - pq.top()[0]

 

pq가 비어있다면 현재 시간 안에서 수행할 작업이 없다는 것으로 다음 작업으로 curTime을 바꿔준다.

 

C++ 코드 :

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

using namespace std;

struct compare
{	//오름차순
    bool operator()(const vector<int>& v1, const vector<int>& v2)
    {
        return v1[1] > v2[1];
    }
};

int solution(vector<vector<int>> jobs) {
    int answer = 0;
    int taskCnt = 0;
    int curTime = 0;
    priority_queue<vector<int>, vector<vector<int>>, compare> pq;
    
    sort(jobs.begin(), jobs.end()); // 작업 소요시간 짧은 순으로 정렬
    while(taskCnt < jobs.size() || !pq.empty()){
        if (taskCnt < jobs.size() && jobs[taskCnt][0] <= curTime) {
            //요청되는 작업 시간이 현재 시간보다 작아야 작업 수행 가능
            pq.push(jobs[taskCnt++]);
            continue;
        }
        if(!pq.empty()) {
            curTime += pq.top()[1]; //소요 시간
            answer += curTime - pq.top()[0]; //요청 시점
            pq.pop();
        }else {
           	// curTime > job[taskCnt] && pq 비어 있는 경우
            // 즉 겹치지 않는 경우
            curTime = jobs[taskCnt][0];
        }
    }
    return answer/jobs.size();
}

결과 :