[ 프로그래머스 디스크 스케쥴러 (Lv3) ] (C++)

프로그래머스의 디스크 스케쥴러 (Lv3) 문제이다.

[ 문제풀이 ]

먼저 요청된 작업들을 어떻게 처리하면 되는지에 대해서부터 알아보자.

문제 설명에도 나와있는 그림을 통해서 모든 작업들을 가장 빠르게 처리하기 위해서는 다음과 같이 2가지 조건을 맞게 작업들을 실행시키면 된다는 것을 알 수 있다.

1. 작업 요청이 들어왔을 때, 현재 실행중인 작업이 없다면, 해당 작업을 바로 실행시킨다.

2. 작업 요청이 들어왔을 때, 현재 실행중인 작업이 있다면, 실행시간이 더 짧은 작업이 더 높은 우선순위를 갖도록 대기시킨다.

위의 조건들에 대해서 구체적으로 알아보자.

1번 조건은 가장 처음 작업 요청에 들어오는 상황을 예로 들 수 있다.

문제 설명과 같이, 0ms시점에 요청이 들어온 3ms가 소요되는 A작업, 1ms시점에 요청이 들어온 9ms가 소요되는 B작업,

2ms시점에 요청이 들어온 6ms가 소요되는 C작업이 있다고 가정해보자.

가장 처음 요청이 들어오는 작업은 'A작업' 이다.

A작업이 들어온 순간에는, 현재 실행되고 있는 작업이 없다. 즉 ! 해당 작업을 바로 실행시키면 된다. 1번 조건에 해당하는

상황이다.

그 다음, 'B작업'에 대한 요청이 들어온 상황을 보자. 현재 'A작업'이 실행되고 있기 때문에, 이 경우에는 'B작업'을 대기시켜 주어야 한다. 그럼 현재 대기열에는 [ B ] 가 존재하게 된다.

그 다음, 'C작업'에 대한 요청이 들어온 상황을 보자. 마찬가지로, 'A작업'이 실행되고 있기 때문에, 'C작업'을 대기열에 추가시켜 주면 된다. 그럼 순서대로 대기열에 넣었다고 생각해보면 [ B C ] 의 순서대로 작업들이 대기하고 있을 것이다.

하지만 ! 이렇게 순차적으로 처리하는 것 보다, "실행시간이 더 짧은 작업을 더 빨리 실행시키는 것"이 평균시간을 더 단축시킬 수 있는 방법이다. 즉 ! [ B C ]가 아닌, 상대적으로 실행시간이 더 짧은 [ C B ]의 형태로 대기열을 형성해 주어야 하는 것이다. 이런식으로 작업들을 처리해주면 평균 처리 시간이 가장 짧은 시간을 구할 수가 있다.

그럼 이 과정을 이제 구현하는 것을 알아보자.

먼저, 1번조건을 만족시키기 위해서 본인은 매개변수로 호출되는 작업들을 "작업 요청이 들어오는 순서" 대로 정렬을 시켜 주었다. 즉 ! 가장 먼저 들어오는 작업이 가장 먼저 실행되도록 만들어 주었다. 가장 먼저 들어오는 작업이라는 것은, 요청이 들어왔을 때 실행중인 작업이 없다는 것을 의미하고, 해당 작업을 바로 실행시키기 위함이다.

두 번째로는 우선순위큐를 이용해서 대기열을 관리해 주었다. 실행시간이 더 짧은 작업일수록 더 높은 우선순위를 가질 수 있도록 우선순위 큐를 이용해서 만들어 주었다. 이 부분을 코드로 보자.

int solution(vector<vector<int>> jobs)
{
    int answer = 0;
    int Time = 0;
    int Idx = 0;
    sort(jobs.begin(), jobs.end(), Cmp);
    priority_queue<pair<int, int>> PQ;
 
    while (Idx < jobs.size() || PQ.empty() == false)
    {
        if (Idx < jobs.size() && Time >= jobs[Idx][0])
        {
            PQ.push(make_pair(-jobs[Idx][1], jobs[Idx][0]));
            Idx++;
            continue;
        }
 
        if (PQ.empty() == false)
        {
            Time = Time + -PQ.top().first;
            answer = answer + (Time - PQ.top().second);
            PQ.pop();
        }
        else Time = jobs[Idx][0];
    }
    return answer / jobs.size();
}

본인이 구현한 코드이다.

line6)에서 보면 가장 먼저, 요청시간이 작은 작업일수록 먼저 처리할 수 있게 정렬시켜주는 과정이다.

line11)에서 보면, 2가지 조건이 있는데, "Idx < jobs.size()" 는 "아직 실행될 작업이 남아있다면" 을 의미한다.

Time >= jobs[Idx][0] 는 "현재 시간이 작업 요청이 들어온 시간보다 크거나 같다면" 을 의미하는데, 이는 즉, 작업 요청이 들어왔는데, 다른 작업을 실행중인 경우를 의미한다. 그 경우에는 line13~15)과 같이, 대기열에 현재 작업을 추가시켜 주게 된다.

물론 이 부분에서 가장 처음 들어온 작업도 대기열에 일단은 추가되게 된다. 하지만 그 다음 반복을 통해서 가장 먼저 실행되게

된다.

line18~23)은 대기열에 있는 작업들을 실행시키기 위해서 대기열에서 하나씩 가져오는 과정이다.

현재 시간은 "작업이 실행되는 시간" 만큼 더해질 것이고, 작업이 진행된 총 시간은 "작업이 실행된 시간 + 작업이 대기했던 시간(Time - PQ.top().second)" 이 되기 때문에, 위와 같이 계산해 주었다.

line24)는 하나의 예외적인 경우를 의미한다. 예를 들어서 현재 시간은 0초인데, 가장 빠르게 들어오는 작업이 a초에 들어온다고 가정해보자(a > 0). 이런 경우에는, 시간을 바로 a초로 만들어 주는 과정이다.

[ 소스코드 ]

#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
 
bool Cmp(vector<int> A, vector<int> B)
{
    if (A[0] < B[0]) return true;
    return false;
}
 
int solution(vector<vector<int>> jobs)
{
    int answer = 0;
    int Time = 0;
    int Idx = 0;
    sort(jobs.begin(), jobs.end(), Cmp);
    priority_queue<pair<int, int>> PQ;
 
    while (Idx < jobs.size() || PQ.empty() == false)
    {
        if (Idx < jobs.size() && Time >= jobs[Idx][0])
        {
            PQ.push(make_pair(-jobs[Idx][1], jobs[Idx][0]));
            Idx++;
            continue;
        }
 
        if (PQ.empty() == false)
        {
            Time = Time + -PQ.top().first;
            answer = answer + (Time - PQ.top().second);
            PQ.pop();
        }
        else Time = jobs[Idx][0];
    }
    return answer / jobs.size();
}