프로그래머스 - 디스크 컨트롤러 (lv2) C++

문제

디스크 컨트롤러

문제 풀이 아이디어

운영체제의 프로세스 스케줄링 알고리즘 중 하나를 구현하는 문제로, 비선점형(Non-preemptive) 방식으로 동작하는 스케줄러를 작성해야 한다.

우선순위 큐를 이용하면 될 것 같다는 것은 운영체제를 공부한 사람이라면 어렵지 않게 알 수 있다. 굳이 운영체제를 공부하지 않았어도 우선순위가 높은 것을 먼저 추출해야 하므로 우선순위 큐를 써야함을 어렵지 않게 알 수 있다.

큰 흐름

각 시간에서 특정 작업을 하게 되면 마치는 시간으로 이동하고 각 작업의 걸린 시간을 answer에 더해놓는다. 마치는 시간으로 이동하는 중에 추가로 생긴 작업들을 pq에 넣어 놓는다. 남은 작업이 없고 pq에도 아무것도 없다면 다 처리한 것이다.

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

struct P {
    int num;
    int start;
    int work;

    bool operator > (const P& o) const {
        if (work != o.work) return work > o.work;
        if (start != o.start) return start > o.start;
        return num > o.num;
    }
};

priority_queue<P, vector<P>, greater<P>> pq;

int solution(vector<vector<int>> jobs) {
    int answer = 0;
    int t = 0;
    int i = 0;
    int n = jobs.size();
    
    sort(jobs.begin(), jobs.end());
    P p = {};
    
    while (1) {
        
        if (pq.empty() && i >= n) {
            // 남은 작업이 없으면 
            break;
        }

        // 특정 시간에 작업 추가
        while (i < n && t >= jobs[i][0]) {
            pq.push({i, jobs[i][0], jobs[i][1]});
            i += 1;
        }
        
        // 각 시간에서 작업을 할 수 있으면
        if (!pq.empty()) {
            p = pq.top();
            pq.pop();
            t += p.work; // 작업 완료 시간으로 이동
            
            answer += t - p.start;
        } else {
            // 현재 시점에 작업할 것이 없으면 
            t = jobs[i][0];
        }
    }
    
    answer = answer / n;
    return answer;
}

나의 문제점

솔직히 금방 구현할 줄 알았다.

중간에 조건문에서 현재 시간과 특정 작업의 시작 시간이 같아야 작업을 할 수 있다고 코드를 작성해놓는 이상한 짓을 해서 안풀렸다. 머리 속으로는 그렇게 생각 안했는데 코드는 왜 그렇게 작성되었는지 모르겠다.

t = jobs[i][0]; 부분을 작성하지 않아서 시간초과가 나기도 했다.