(프로그래머스) 디스크 컨트롤러

문제 링크

• 프로그래머스

요약

• Idle time 처리 잘 해주기

최종 §

결과

• 대단한 아이디어는 없고 구현문제에 가깝다.
  • jobs 를 request time으로 정렬해서 어디까지 queue에 넣어놨는지 기억
  • jobs 에서 현재 timestamp 기준 request된 job 들을 전부 pq에 넣음
  • pq에서 하나를 꺼내어 처리하고 처리 시간만큼 ts 증가

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
 
using namespace std;
 
#define PACK(duration, req_time, id) (((duration) << 20) | ((req_time) << 10) | (id))
#define UNPACK_DURATION(pack) (((pack) >> 20) & 0x3FF)
#define UNPACK_REQ_TIME(pack) (((pack) >> 10) & 0x3FF)
#define UNPACK_ID(pack) ((pack) & 0x3FF)
 
#define REQ_TIME_IDX (0)
#define DURATION_IDX (1)
#define PACK_IDX (1)
 
#define MAX(a, b) ((a) > (b) ? (a) : (b))
 
int solution(vector<vector<int>> jobs) {
    int ts = 0;
    int iter = 0;
    priority_queue<int, vector<int>, greater<int>> pq;
    int ta_acc = 0;
 
    for (int i = 0; i < jobs.size(); i++) {
        jobs[i][PACK_IDX] = PACK(jobs[i][DURATION_IDX], jobs[i][REQ_TIME_IDX], i);
    }
 
    sort(jobs.begin(), jobs.end(), [](auto &a, auto &b) {
        return a[REQ_TIME_IDX] < b[REQ_TIME_IDX];
    });
 
    ts = jobs[iter][REQ_TIME_IDX];
    for (int i = iter; i < jobs.size(); i++) {
        if (jobs[i][REQ_TIME_IDX] <= ts) {
            pq.push(jobs[i][PACK_IDX]);
            iter = i + 1;
        } else {
            break;
        }
    }
 
    while (!pq.empty()) {
        int pack = pq.top();
 
        pq.pop();
 
        ts += UNPACK_DURATION(pack);
        ta_acc += ts - UNPACK_REQ_TIME(pack);
 
        for (int i = iter; i < jobs.size(); i++) {
            if (jobs[i][REQ_TIME_IDX] <= ts) {
                pq.push(jobs[i][PACK_IDX]);
                iter = i + 1;
            } else {
                break;
            }
        }
 
        if (pq.empty() && iter < jobs.size()) {
            ts = jobs[iter][REQ_TIME_IDX];
            for (int i = iter; i < jobs.size(); i++) {
                if (jobs[i][REQ_TIME_IDX] <= ts) {
                    pq.push(jobs[i][PACK_IDX]);
                    iter = i + 1;
                } else {
                    break;
                }
            }
        }
    }
 
    return ta_acc / jobs.size();
}

• 다만 주의할 점은 highlight로 표시한 idle time에 대한 처리이다.
  • 만약 job들을 다 처리하지 않았는데, pq에 아무것도 없으면 현재 idle 상태인 것.
  • 따라서 이 때는 다음 job의 request time으로 ts를 움직인 다음 pq에 job들을 넣어주면 된다.