[프로그래머스] PCCP 모의고사 4번 - 운영체제 (C++)

https://school.programmers.co.kr/learn/courses/20847/lessons/255903

 

우선순위큐를 사용해야겠다는 생각이 매우 쌔게 드는 문제이고 써야하는게 맞다.

그러나 어떻게 써야하는지가 중요한데, 우선순위에 따라서 프로그램을 실행시키지만 무조건 우선순위만 따지는 것이 아닌 호출시간도 하나의 조건이 된다. 그러므로 두개의 우선순위큐를 만들어야한다.

 

1. 호출시간이 빠를 수록 먼저 나오는 우선순위큐

2. 우선순위에 따른 우선순위큐

 

먼저 1번에 모든 프로그램을 넣어놓는다. 그리고 now = 0 으로 세팅한다.

 

그리고 현재 시간에 실행할 수 있는 프로그램을 모두 넣어놓는다. 그리고 우선순위에 따라 한가지 프로그램을 진행하고 그 때 시간에 맞는 것들을 또 넣어놓는다. 이것을 1번 우선순위큐가 빌 때 까지 진행하고 마지막엔 2번 우선순위큐가 빌 때 까지 시간과 정답을 갱신한다.

 

우선순위 큐 문제중에선 이렇게 처음부터 넣어놓는게 아니라 일부를 넣었다가 빼고 넣었다가 빼는 식의 문제가 난이도가 있는 것 같다. 다시 보면 좋을 문제

 

#include <string>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;

priority_queue<pair<int, pair<int, int>>> startQueue;
priority_queue<pair<int, pair<int, int>>> runQueue;

vector<long long> solution(vector<vector<int>> program) {
    vector<long long> answer(11, 0);
    
    for(int i = 0; i < program.size(); i++){
        startQueue.push({-program[i][1],{program[i][0], program[i][2]}});
    }
    
    int now = 0;
    
    while(!startQueue.empty()){
        int level = startQueue.top().second.first;
        int start = -startQueue.top().first;
        int process = startQueue.top().second.second;
        if(now >= start){
            startQueue.pop();
            runQueue.push({-level, {-start, process}});
        }else{
            if(runQueue.empty()){
                now++;
            }else{
                int runStart = -runQueue.top().second.first;
                int runProcess = runQueue.top().second.second;
                int runLevel = -runQueue.top().first;
                runQueue.pop();

                answer[runLevel] += (now - runStart);
                now += runProcess;
            }
        }
    }
    
    while(!runQueue.empty()){
        int runStart = -runQueue.top().second.first;
        int runProcess = runQueue.top().second.second;
        int runLevel = -runQueue.top().first;
        runQueue.pop();

        answer[runLevel] += (now - runStart);
        now += runProcess;
    }
    
    answer[0] = now;
    
    return answer;
}