[c++] Programmers - PCCP 모의고사 1회 4번 운영체제

PCCP 모의고사 1회 4번 유전법칙

priority_queue의 compare 구조체를 만들 수 있는 사람에게는 어렵지 않은 문제였을것.
백준 회의실 배정문제와 유사하다고 생각되었음.

본인은 compare 구조체를 하나만 쓰기위해 compare 안에서 전역변수를 참조하도록 코드를 짰는데, 그렇게 하면 오류가 생긴다,, 고 한다.

그래서 로직을 변경해서 우선순위 큐 2개를 씀

1. 실행순서가 기준인 priority_queue ->pq
2. 우선순위가 기준인 priority_queue ->pq2

priority_queue compare 구조체

struct CompareVector {
    bool operator()(const vector<long long>& a, const vector<long long>& b){
        if (a[1] == b[1])
            return a[0] > b[0];
        else
            return a[1] > b[1];
    }
};

struct CompareVector2{
    bool operator()(const vector<long long>& a, const vector<long long>& b){
        if (a[0] == b[0])
            return a[1] > b[1];
        else
            return a[0] > b[0];
    }
};

반복

1. pq 에서 현재 시간을 기준으로 실행할 수 있는 프로그램을 꺼내서 pq2 에 push
2. pq2 에 원소가 있다면 top을 꺼내서 갱신
   2-1. 이때 현재시간보다 실행시간이 빠르다면 지연 시간 갱신
3. pq2 가 비어있다면 현재시간에 실행시킬 수 있는 프로그램이 없는 것. pq의 top을 꺼내서 현재시간 갱신
4. 종료후 현재 시간을 answer에 갱신! 끗!

code

#include <string>
#include <vector>
#include <iostream>
#include <queue>

using namespace std;

struct CompareVector {
    bool operator()(const vector<long long>& a, const vector<long long>& b){
        if (a[1] == b[1])
            return a[0] > b[0];
        else
            return a[1] > b[1];
    }
};

struct CompareVector2{
    bool operator()(const vector<long long>& a, const vector<long long>& b){
        if (a[0] == b[0])
            return a[1] > b[1];
        else
            return a[0] > b[0];
    }
};

priority_queue<vector<long long>, vector<vector<long long>>, CompareVector> pq;
priority_queue<vector<long long>, vector<vector<long long>>, CompareVector2> pq2;

vector<long long> solution(vector<vector<int>> program) {
    vector<long long> answer;
    
    for(int i=0; i<11; i++)
        answer.push_back(0);
    
    for (int i=0; i<program.size(); i++)
    {
        vector<long long> temp;
        temp.push_back(program[i][0]);
        temp.push_back(program[i][1]);
        temp.push_back(program[i][2]);
        pq.push(temp);
        
        temp = pq.top();
    }
    
    long long nowtime = 0;

    while (!pq.empty() || !pq2.empty())
    {
        vector <long long> v;
        
        while (!pq.empty())
        {
            v = pq.top();
            if (v[1] > nowtime)
                break;
            pq2.push(v);
            pq.pop();
        }
        
        if (pq2.empty())
        {
            v = pq.top();
            nowtime = v[1] + v[2];
            pq.pop();
        }
        else
        {
            v = pq2.top();
            if (nowtime > v[1])
            {
                answer[v[0]] += (nowtime - v[1]);
                nowtime += v[2];
            }
            else
                nowtime += v[2];
            pq2.pop();
        }
    }

    answer[0] = nowtime;

    return answer;
}