[프로그래머스 코딩테스트 고득점 Kit - 힙(Heap)] 디스크 컨트롤러

구현 문제

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

 

---

[문제 풀이]

 

모든 작업에 대해 (작업이 끝난 시간) - (작업이 요청된 시간)의 합을 최소로 만드는 문제입니다.

하나의 디스크는 하나의 작업만 처리가 가능합니다.

 

작업 시간이 전혀 겹치지 않는다면 이 문제는 전혀 문제가 아닙니다.

그러나 작업 시간이 겹치는 경우에 어느 작업부터 시작해야 하는지 골라야 하는 것이 어려운 문제입니다.

 

(작업이 끝난 시간) - (작업이 요청된 시간)만 보면 생각하기 쉽지 않으니 조금 형태를 바꿔보겠습니다.

(작업이 끝난 시간) - (작업이 요청된 시간)은 (작업을 수행하는 시간) + (현재 시간) - (작업이 요청된 시간)으로 치환할 수 있습니다.

 

이해가 안 될 수도 있으니 그림으로 표현해보겠습니다.

 

작업 A가 끝난 후

위의 그림은 작업 A가 끝난 후의 상황이라고 가정하겠습니다.

0초에서 5초간 실행되는 작업 A가 끝났으므로 현재 시간은 5초입니다.

 

그리고 작업 B를 실행합니다.

B의 요청은 2초에 들어온 것을 확인할 수 있으나 A가 끝나지 않아 실질적으로는 현재 시간인 5초부터 9초간 14초까지 작업을 수행하였습니다.

 

B의 (작업이 끝난 시간) - (작업이 요청된 시간)은 14 - 2 = 12라는 것을 알 수 있습니다.

위에서 (작업이 끝난 시간) - (작업이 요청된 시간) = (작업을 수행하는 시간) + (현재 시간) - (작업이 요청된 시간)라고 하였습니다.

(작업을 수행하는 시간) + (현재 시간) - (작업이 요청된 시간) = 9 + 5 - 2 = 12로 동일함을 알 수 있습니다.

 

시각화해서 보니 매우 당연하게 치환이 되는 것을 알 수 있습니다.

 

 

굳이 더 긴 식으로 치환한 이유가 무엇일까요?

(작업을 수행하는 시간) + (현재 시간) - (작업이 요청된 시간)

위 식을 자세히 보면 현재 시간만 가변적입니다.

 

작업이 서로 겹치지 않는다면 현재 시간 역시 고정적입니다.

그래서 작업이 겹치지 않으면 문제가 되지 않는다고 위에서 언급한 것입니다.

 

하지만 작업이 서로 겹치게 된다면 어떤 작업부터 시작했는지에 따라 현재 시간을 최소로 만들 수 있을 겁니다.

작업이 겹치는 경우에 현재 시간은 이전까지의 작업이 걸리는 시간에 따라 변합니다.

 

작업이 서로 겹친 경우에 현재 시간은 이전까지의 작업을 마치고 난 뒤의 시간입니다.

이전에 0초에서부터 3초짜리와 5초짜리 작업을 하게 됐다면 현재 시간은 8초일 것이고 4초와 5초짜리 작업을 하게 됐다면 현재 시간은 9초일 것입니다.

즉 이전에 고른 작업이 걸리는 시간이 현재 시간을 단축시킬 수 있는 요소이고, 당연하게도 작업이 겹치는 상황에서는 더 짧게 걸리는 작업을 먼저 수행할수록 현재 시간이 단축될 것입니다.

 

그러므로 디스크에 처리해야 하는 작업이 쌓인 경우 짧게 끝나는 것부터 처리하고 현재 시간을 계속 업데이트해주면 됩니다.

현재 시간을 계속 업데이트 하면서 현재 시간보다 이전에 요청된 작업 (겹치는 작업)이 존재한다면 디스크에 계속 작업을 넣어주도록 합니다.

 

디스크에 계속 작업을 넣어가면서 가장 짧게 끝나는 작업을 찾아내는 과정을 효율적으로 처리하기 위해 우선순위 큐를 사용합니다.

디스크가 우선순위 큐라고 생각하면 됩니다.

 

 

이제 디스크에 언제 넣고 빼는지, 어떻게 넣고 빼는지에 관한 내용이 끝났으니 작업들을 어떻게 넣을지 생각합시다.

작업들을 그냥 받아와서 디스크에 넣으면 안 됩니다.

문제의 그 어디에도 시작시간을 기준으로 정렬되어 있다는 명시가 없으므로 시작 시간을 기준으로 정렬해 줄 필요가 있습니다.

디스크에 관한 내용은 클래스(구조체) 혹은 pair로 저장하면 됩니다. (시작 시간, 걸린 시간)

 

정렬을 할 때 주의사항은 시작 시간으로만 정렬하면 안 됩니다.

같은 시간에 시작하는 작업이 중복으로 주어지지 않는다는 조건이 없으므로 이 또한 고려해야 합니다.

그러므로 시작 시간이 같다면 더 짧게 끝나는 작업으로 정렬해줘야 합니다.

 

혹시나 왜 정렬을 하는지가 궁금하다면 아래의 두 가지의 이유가 있습니다.

 

• 문제 조건에 적힌 우선 디스크가 작업을 수행하지 않는 경우 먼저 요청이 들어온 작업부터 처리합니다.
• 현재 시간 이전에 요청된 모든 작업을 디스크에 넣어야 하므로 정렬을 하는 것이 편합니다.

평균을 내야 하는 문제이므로 answer를 jobs의 길이로 나눠주고 return하여야 합니다.

소수점 아래는 버리므로 그냥 int 나누기 연산을 사용합니다. 파이썬은 //를 사용하면 됩니다.

 

정리하자면

• 요청된 시간 순으로 정렬하여 확인
• 시간이 겹친다면 우선 순위 큐에 넣고 작업을 진행, 그렇지 않다면 가장 앞쪽의 작업을 진행
• 하나씩 작업을 진행하면서 현재 시간을 갱신

의 과정으로 풀이가 가능합니다.

 

---

[소스 코드] / C++

 

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

using namespace std;

class Disk {
public:
    int s, t;
    
    Disk(int s, int t) {
        this->s = s;
        this->t = t;
    }
    
    bool operator<(const Disk& d) const {
        return this->t > d.t;
    }
};

bool cmp(const Disk& d1, const Disk& d2) {
    if (d1.s == d2.s) return d1.t < d2.t;
    return d1.s < d2.s;
}

int solution(vector<vector<int>> jobs) {
    int answer = 0, N = jobs.size(), currentTime = 0;
    vector<Disk> disks;
    priority_queue<Disk> pq;
    
    for (int i = 0; i < N; i++) {
        vector<int> v = jobs[i];
        int s = v[0], t = v[1];
        disks.push_back(Disk(s, t));
    }
    
    sort(disks.begin(), disks.end(), cmp);
    
    int i = 0;
    for (int j = 0; j < N; j++) {
        while (i < N) {
            Disk cur = disks[i];
            int s = cur.s, t = cur.t;
            
            if (s >= currentTime) break;

            pq.push(cur);
            i++;
        }
        
        if (pq.empty()) {
            Disk cur = disks[i++];
            int s = cur.s, t = cur.t;
            currentTime = s + t;
            answer += t;
        }
        else {
            Disk cur = pq.top();
            int s = cur.s, t = cur.t;
            pq.pop();
            
            currentTime += t;
            answer += currentTime - s;
        }
    }
    
    return answer / N;
}