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

코딩테스트 연습 - 디스크 컨트롤러 바로가기

문제 설명

문제 풀이

최대힙을 사용하는 우선순위 큐는 top 에 있는 원소를 꺼낼 때, O(1) 시간이 소요됨을 활용하고자 하였습니다.

struct Comp {
    bool operator()(vector<int> lhs, vector<int> rhs) {
        return lhs.at(1) > rhs.at(1);
    }
};

int solution(vector<vector<int>> jobs) {
    int answer = 0;
    int curr_job = 0, curr_time = 0;
    sort(jobs.begin(), jobs.end());

    priority_queue<vector<int>, vector<vector<int>>, Comp> pq;
    while (curr_job < jobs.size() || !pq.empty()) {
        if (jobs.size() > curr_job && curr_time >= jobs[curr_job][0]) {
            pq.push(jobs[++curr_job]);
            continue;
        }
        else if (!pq.empty()) {
            curr_time += pq.top()[1];
            answer += (curr_time - pq.top()[0]);
            pq.pop();
        }
        else {
            curr_time = jobs[curr_job][0];
        }
    }
    return (answer / (int)jobs.size());
}