[알고리즘C++] 디스크 컨트롤러

오늘의 문제

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

디스크 컨트롤러

나의 풀이

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

using namespace std;

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

모범 답안

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

using namespace std;

bool compare(vector<int> a, vector<int> b){
    return a[1] < b[1];
}

int solution(vector<vector<int>> jobs) {
    int answer = 0;
    int start = 0; // 현재까지 작업이 진행된 시간
    int time = 0; // 각각의 작업이 진행되는데 걸린 시간들의 합
    int size = jobs.size();

    sort(jobs.begin(), jobs.end(), compare); // 소요시간으로 우선 배열

    while(!jobs.empty()){
        for(int i=0; i<jobs.size(); i++){
            if(jobs[i][0] <= start) {
                start += jobs[i][1];
                time += start - jobs[i][0];
                jobs.erase(jobs.begin() + i);
                break;
            }

            if(i == jobs.size()-1) start++;
        }
    }

    answer = time / size;
    return answer;
}

배울 점

• 오래걸린 이유: 입력이 순서대로 들어오는 줄 알음.. 같은 로직으로 정렬을 하지 않고 실행했을 때 개 오답이 나와서 하.. 이게 아닌가.. 하고 삽질하다가 어제 저녁에 풀다가 오늘 정답을 받게 되었다