[프로그래머스] 디스크 컨트롤러 (Lv. 3) C++ 풀이

문제 링크

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

분류

Heap, SJF(Shortest Job First), Priority Queue

시도한 방법

문제는가상의 스케줄러를 만드는 일이다.

가정에서는 중간중간에 발생하는 Context Switching에 걸리는 시간이 없다고 명시되어 있으므로, 단순히 작업하는 데 걸리는 시간의 총합을 반환하면 된다.

 

문제의 핵심은 잔여시간이 긴 작업이 처리되고 있을 경우, 다른 작업들은 계속 기다리기만 해야 한다는 점이다.

이 부분은 전체 turn-around time을 크게 저해할 수 있으므로, 모든 작업이 끝났을 때 완료까지 걸리는 시간이 가장 짧은 작업을 우선해서 처리해야 한다고 해석할 수 있다.

위 구조로 이루어진 알고리즘을 Shortest Job First 라고 한다. (참고 링크)

 

위 가정을 구현하는 가장 쉬운 방법은 우선순위 큐를 활용하는 방법이다.

작업 대기 큐를 priority queue로 만들어서 작업에 소요되는 시간이 낮은 작업에 높은 우선순위를 보유하면 된다.

이렇게 디자인할 경우, 작업 대기 큐에 소요시간이 낮은 작업부터 적재되므로 따로 비교나 정렬연산을 작성해줄 필요 없이 문제를 해결할 수 있다.

 

당연하게도, 실제로 어떤 작업을 수행해야 할지는 관심가질 필요가 (여기서는)없기 때문에 지나고 있는 시간만 더해주면 답이 나올 수 있겠다.

 

결과 코드

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

using namespace std;

struct process
{
    int id;
    int meaningTime;
    int inputTime;
    process(int id, int inputTime, int meaningTime) : id(id), inputTime(inputTime), meaningTime(meaningTime)  {}
};

bool compare(process a, process b)
{
    return a.inputTime < b.inputTime;
}

struct cmp
{
    bool operator()(process p1, process p2)
    {
        if (p1.meaningTime == p2.meaningTime)
        {
            if (p1.inputTime == p2.inputTime)
                return p1.id > p2.id;
            return p1.inputTime > p2.inputTime;
        }
        return p1.meaningTime > p2.meaningTime;
    }
};

bool operator<(process p1, process p2)
{
    if (p1.meaningTime == p2.meaningTime)
    {
        if (p1.inputTime == p2.inputTime)
            return p1.id > p2.id;
        return p1.inputTime > p2.inputTime;
    }
    return p1.meaningTime > p2.meaningTime;
}
int solution(vector<vector<int>> jobs)
{
    int answer = 0;
    priority_queue<process, vector<process>, cmp> readyQueue;
    vector<process> idle;

    for (int i = 0; i < jobs.size(); i++)
        idle.push_back(process(i, jobs[i][0], jobs[i][1]));

    int clock = 0;
    int averageTurnaroundTime = 0;
    int index = 0;
    sort(idle.begin(), idle.end(), compare);

    while (true)
    {
        if (index == idle.size() && readyQueue.empty())
            break;

        while (index < idle.size() && idle[index].inputTime <= clock)
        {
            readyQueue.push(idle[index]);
            index++;
        }

        if (readyQueue.empty())
        {
            clock = idle[index].inputTime;
            continue;
        }

        int turnaroundTime = 0;
        process running = readyQueue.top();
        readyQueue.pop();

        if (clock < running.inputTime)
            clock = running.inputTime;

        clock += running.meaningTime;
        turnaroundTime = clock - running.inputTime;
        averageTurnaroundTime += turnaroundTime;
    }

    answer = static_cast<int>(averageTurnaroundTime / jobs.size());

    return answer;
}

 

실행 결과