[프로그래머스]디스크 컨트롤러

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

 

프로그래머스

문제 설명보다는 기존 다른 코드와 다른 점을 설명하고자 한다.
https://school.programmers.co.kr/learn/courses/14743/lessons/118891

프로그래머스

 
위 링크에서 문제에서 조금 더 고려해야 하는 부분을 알아두는 것이 좋다.
내 소감은 이렇게 풀면 안 되지만 Heap을 사용하는 문제라, Heap을 어떤 용도로 사용할까? 란 것에 초점을 맞췄다.
하지만 Heap 무조건 넣으면 안 되고, 각 요소마다 값이 2개씩이 있고 어느 쪽으로 정렬해서 넣어야 하는지 애매한 부분이 많았다.

#include <vector>
#include <iostream>
#include <queue>
#include <algorithm>
 
using namespace std;
 
struct cmp {
    bool operator()(vector<int> a, vector<int> b) {
        return a.at(1) > b.at(1);
    }
};
 
int solution(vector<vector<int>> jobs) {
    int answer = 0, j = 0, time = 0;
    sort(jobs.begin(), jobs.end());
    priority_queue<vector<int>, vector<vector<int>>, cmp> pq;
    while (j < jobs.size() || !pq.empty()) {
        if (jobs.size() > j && time >= jobs[j][0]) {
            pq.push(jobs[j++]);
            continue;
        }
        if (!pq.empty()) {
            time += pq.top()[1];
            answer += time - pq.top()[0];
            pq.pop();
        }
        else
            time = jobs[j][0];
    }
    return answer / jobs.size();
}

다른 분들의 코드를 보면 jobs을 한번 정렬해서 시간 순으로 만든다. 그리고 난 뒤 job을 훑어가면서 내 시간에 따라 heap에 넣고, heap에서 시간 계산을 해나가며 내 상태 값을 변경해 나간다.
그리고 heap에 값이 없는 경우에는 시간을 변경한다.
나는 Job을 정렬하는 것이 마음에 들지 않았다.

결국 Job을 정렬한다는 의미는 Heap을 사용해도 된다는 의미로 생각이 들었다.
그리고 무엇보다도 while문이 두 가지 행위를 한번에 하고 있었다. 
1. job을 돌기
2.Heap 체킹
어쩔 수 없이 heap에서 값을 빼내가며 상태값을 바꿔야 한다. 그래도 분리하고 싶어서 최대한 분리해봤다.

#include <vector>
#include <iostream>
#include <queue>
#include <algorithm>
#include <iostream>
using namespace std;
 
struct pairFirstASC {
    bool operator()(const pair<int, int> &a, const pair<int, int> &b) {
        return a.first > b.first;
    }
};

struct pairSecondASC {
    bool operator()(const pair<int, int> &a, const pair<int, int> &b) {
        return a.second > b.second;
    }
};

int solution(vector<vector<int>> jobs) {
    int answer = 0;

    priority_queue<pair<int, int>, vector<pair<int, int>>, pairFirstASC> pq;
    priority_queue<pair<int, int>, vector<pair<int, int>>, pairSecondASC> pq2;
    
    for(vector<int> job: jobs) {
        pq.push({job[0], job[1]});
    } 
   
    int curTime = 0;
    
    while(!pq.empty()) {
        while(!pq.empty() && pq.top().first <= curTime) {
            pq2.push(pq.top());
            pq.pop();
        }
        
        if(pq2.empty()) {
            curTime = pq.top().first;
        } else if(!pq2.empty()) {
            curTime += pq2.top().second;
            answer += curTime - pq2.top().first;
            pq2.pop();
        }
    }
    
    while(!pq2.empty()) {
        curTime += pq2.top().second;
        answer += curTime - pq2.top().first;
        pq2.pop();
    }
    
    return answer / jobs.size();
}

코드가 더 늘어나긴 했지만, 재밌는 도전이었던 것 같다.