C++ / 프로그래머스 / 1회 모의고사 - 운영체제

문제

 

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

문제풀이

 

프로그램의 우선순위는 점수가 낮은 프로그램이 가장 먼저,

점수가 같다면 먼저 호출된 프로그램이 우선순위가 높아진다.

 

먼저 주어진 2차원 벡터 program을 호출된 시각 오름차순으로 정렬을 한다.

while문을 이용해 프로그램끼리 비교할 예정이므로 점수, 실행 시간순으로 정렬은 필요가 없다.

 

우선순위큐를  선언하고 따로 순서를 정하는 조건을 세운다.

문제에서 주어진 대로 점수를 먼저, 점수가 같다면 먼저 호출된 프로그램이 top부분에 있도록 한다.

 

다음은 모든 프로그램을 탐색할 수 있게 while문을 작성한다.

만약 우선순위큐가 비어있거나 현재 시각이 프로그램의 호출 시각을 지났다면,

우선순위 큐에 해당 프로그램 번호와 점수를 push 한다.

 

        program_idx = pq.top().second;
        pq.pop();

        answer[program[program_idx][0]] += time - program[program_idx][1];
        time += program[program_idx][2];

 

그다음은 해당 프로그램을 실행시키는 부분이다.

우선순위큐의 top의 프로그램을 실행시킨다.

answer에는 프로그램의 점수마다 대기시간의 합을 저장해야 한다.

현재 시각 - 프로그램의 호출 시간을 프로그램의 점수에 해당하는 answer의 인덱스가 누적 합한다.

프로그램을 실행했으므로 시간에 프로그램 실행시간을 더한다.

 

    while (!pq.empty()) {
        program_idx = pq.top().second;
        pq.pop();

        answer[program[program_idx][0]] += time - program[program_idx][1];
        time += program[program_idx][2];
    }

    answer[0] = time;

 

while문이 종료됐을 때 우선순위큐가 비어있지 않는 경우도 있다.

따라서 위의 행동을 똑같이 하면 된다.

마지막으로 answer[0]은 모든 프로그램이 종료되는 시각인 time을 저장하면 된다.

 

 

코드

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#define pii pair<int, int>
using namespace std;

struct cmp1 {
    bool operator()(pii& p1, pii& p2) {
        if (p1.first == p2.first) return p1.second > p2.second;
        return p1.first > p2.first;
    }
};

bool cmp2(vector<int>& v1, vector<int>& v2) {
    return v1[1] < v2[1];
}

vector<long long> solution(vector<vector<int>> program) {
    vector<long long> answer(11, 0);
    priority_queue<pii, vector<pii>, cmp1>pq;
    sort(program.begin(), program.end(), cmp2);

    int program_idx(0), idx(0), time(0);

    while (idx < program.size()) {
        while (idx < program.size() && (pq.empty() || time >= program[idx][1])) {
            if (pq.empty() && time < program[idx][1]) {
                time = program[idx][1];
            }
            pq.push({ program[idx][0] , idx });
            ++idx;
        }

        program_idx = pq.top().second;
        pq.pop();

        answer[program[program_idx][0]] += time - program[program_idx][1];
        time += program[program_idx][2];
    }

    while (!pq.empty()) {
        program_idx = pq.top().second;
        pq.pop();

        answer[program[program_idx][0]] += time - program[program_idx][1];
        time += program[program_idx][2];
    }

    answer[0] = time;
    return answer;
}