프로그래머스 문제 - 디스크 컨트롤러

프로그래머스 디스크 컨트롤러 문제 풀이를 진행하였습니다.

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

한번에 하나의 작업만 가능한 하드디스크가 존재합니다.
어느 시점에 얼마나 소요되는지 알려주는 요청이 배열로 주어집니다.
주어진 요청들의 작업 순서에 따라 종료까지 걸린 시간의 평균이 달라집니다.
제일 적은 작업 시간의 평균을 구해야합니다.

문제 풀이

모든 작업을 끝낸 시간이 제일 적도록 해야 합니다.

일단 요청이 빠른 순서대로 작업을 해야 작업 시간이 줄어들기 때문에 배열을 오름차순으로 정렬해줍니다.
처음의 작업은 제일 빨리 요청한 작업부터 시작합니다. 즉 배열의 0번째에 있는 작업을 먼저 시작해줍니다.
작업이 끝나게 되면 끝나는 시간 t와 현재까지 작업한 시간을 알 수 있습니다.

하나의 작업이 끝날 때마다 요청된 작업들 중 제일 빨리 끝나는 작업부터 끝내주도록 합니다.
만약 한 작업이 끝나서 3초가 되었고, 1초때에 요청한 9초짜리 작업과 2초때에 요청한 6초짜리 작업이 있다면 2초때에 요청한 6초짜리 작업을 먼저 끝내고 시간을 갱신한 뒤 요청된 작업들 중에서 다시 비교하여 작업을 진행해야 합니다.

이런 식으로 모든 작업을 끝낸 후 나온 시간을 작업의 갯수만큼 나누어주면 됩니다.

전체 코드

priority_queue를 struct를 통해 좀 더 유용하게 사용할 수 있는 방법을 배웠습니다.

#include <bits/stdc++.h>
#include <string>
#include <vector>

using namespace std;

struct process{
    int processTime;
    int startTime;
    int index;
    process(int a, int b, int c) : processTime(a), startTime(b), index(c)   {}
};

struct compare {
    bool operator()(process a, process b) {
        if(a.processTime > b.processTime)
        {
            return true;
        }else{
            if(a.processTime == b.processTime)
            {
                return a.startTime > b.startTime;
            }
            return false;
        }
    }
};

int solution(vector<vector<int>> jobs) {
    int answer = 0;
    int time = 0;
    priority_queue<process, vector<process>, compare> pq;
    
    sort(jobs.begin(), jobs.end());
    
    answer = jobs[0][1];
    time = jobs[0][0] + jobs[0][1];
    
    int n = 1;
    while(n < jobs.size())
    {
        if(time >= jobs[n][0])
        {
            pq.push(process(jobs[n][1], jobs[n][0], n));
            n++;
        }
        else
        {
            if(pq.empty())
            {
                //바로 다음 처리 시간만큼 진행
                answer += jobs[n][1];
                time += (jobs[n][0] - time) + jobs[n][1];
                n++;
            }else
            {
                //대기가 짧은 순서대로, 같으면 처리시간이 적은 순으로 계산
                process cur = pq.top();
                pq.pop();
                answer += (time - jobs[cur.index][0]) + jobs[cur.index][1];
                time += jobs[cur.index][1];
            }
        }
    }
    while(!pq.empty())
    {
        //대기가 짧은 순서대로, 같으면 처리시간이 적은 순으로 계산
        process cur = pq.top();
        pq.pop();
        answer += (time - jobs[cur.index][0]) + jobs[cur.index][1];
        time += jobs[cur.index][1];
    }
    
    answer = answer / jobs.size();
    
    return answer;
}

출저

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