[프로그래머스] 디스크 컨트롤 (level3, c++)

 

문제

---

하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다.

예를들어

- 0ms 시점에 3ms가 소요되는 A작업 요청 - 1ms 시점에 9ms가 소요되는 B작업 요청 - 2ms 시점에 6ms가 소요되는 C작업 요청

와 같은 요청이 들어왔습니다. 이를 그림으로 표현하면 아래와 같습니다.

한 번에 하나의 요청만을 수행할 수 있기 때문에 각각의 작업을 요청받은 순서대로 처리하면 다음과 같이 처리 됩니다.

- A: 3ms 시점에 작업 완료 (요청에서 종료까지 : 3ms) - B: 1ms부터 대기하다가, 3ms 시점에 작업을 시작해서 12ms 시점에 작업 완료(요청에서 종료까지 : 11ms) - C: 2ms부터 대기하다가, 12ms 시점에 작업을 시작해서 18ms 시점에 작업 완료(요청에서 종료까지 : 16ms)

이 때 각 작업의 요청부터 종료까지 걸린 시간의 평균은 10ms(= (3 + 11 + 16) / 3)가 됩니다.

하지만 A → C → B 순서대로 처리하면

- A: 3ms 시점에 작업 완료(요청에서 종료까지 : 3ms) - C: 2ms부터 대기하다가, 3ms 시점에 작업을 시작해서 9ms 시점에 작업 완료(요청에서 종료까지 : 7ms) - B: 1ms부터 대기하다가, 9ms 시점에 작업을 시작해서 18ms 시점에 작업 완료(요청에서 종료까지 : 17ms)

이렇게 A → C → B의 순서로 처리하면 각 작업의 요청부터 종료까지 걸린 시간의 평균은 9ms(= (3 + 7 + 17) / 3)가 됩니다.

각 작업에 대해 [작업이 요청되는 시점, 작업의 소요시간]을 담은 2차원 배열 jobs가 매개변수로 주어질 때, 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리하면 평균이 얼마가 되는지 return 하도록 solution 함수를 작성해주세요. (단, 소수점 이하의 수는 버립니다)

 

문제조건

---

• jobs의 길이는 1 이상 500 이하입니다.
• jobs의 각 행은 하나의 작업에 대한 [작업이 요청되는 시점, 작업의 소요시간] 입니다.
• 각 작업에 대해 작업이 요청되는 시간은 0 이상 1,000 이하입니다.
• 각 작업에 대해 작업의 소요시간은 1 이상 1,000 이하입니다.
• 하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다.

 

풀이

---

문제에서 주어진대로 그때그때 가장 짧은 길이의 작업을 실행하면 된다. 우선 빨리 들어오는 작업을 먼저 실행해야 함으로 jobs들을 들어오는 시간에 따라 정렬한다. 한 작업이 끝났을때 대기열에 있는 작업들은 작업의 길이에 따라 정렬해준다. 매번 정렬을 하지 않기 위해서 priority_queue를 사용해 주었다. 단, 길이가 짧은 순으로 정렬되어야 하기때문에 {-jobs[i][1], jobs[i][0]}으로 음수로 만들어 넣어주었다(길이가 0인 작업이 없기때문에 사용가능).

그냥 vector로 푸는 방법도 시도해보았는데 조건이 빡빡하지 않아서 그냥 vector로 넣은 후 sort해주어도 시간 초과가 나지 않았다. priority_queue에 익숙하지 않아서 내림차순을 음수로 표현해서 풀어주었는데 다른 방법도 공부해 보아야겠다.

코드

---

priority_queue

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

using namespace std;

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

 

vector

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

using namespace std;

int solution(vector<vector<int>> jobs) {
    int answer = 0;
    vector<pair<int, int>> pq;
    sort(jobs.begin(), jobs.end());
    
    int t = 0;
    int i = 0;
    while(i<jobs.size() || !pq.empty()){
        if(i < jobs.size() && t>=jobs[i][0]){
            pq.push_back({jobs[i][1], jobs[i][0]});
            sort(pq.begin(), pq.end());
            i++;
            continue;
        }
        if(!pq.empty()){
            t+=pq[0].first;
            answer+=t-pq[0].second;
            pq.erase(pq.begin());
        }
        else t=jobs[i][0];
    }
    return answer/jobs.size();
}