[C++/PGS] [PCCP 모의고사 #1] 4번 - 운영체제

 

https://school.programmers.co.kr/learn/courses/15008/lessons/121686#

프로그래머스

---

프로그래머스 PCCP 모의고사 1회 - 4번

소요시간 약 59분 😱

자료구조(heap), 우선순위 큐 유형, 추정 난이도는 level 3 - 쉬운 4까지

 

최근에 프로그래머스의 레벨 3 문제인

'디스크 컨트롤러 문제(https://xxilliant.tistory.com/310)'를 풀어봤던 게 큰 도움이 되었다.

이거 안해봤으면 ㄹㅇ 삽질 엄청 했을듯,,,

 

도착시간이 되면 들어오는 값들 중에서 우선순위를 지정해줘야 하므로 priority queue를 사용해주었다.

정렬은 struct 선언 후, bool operator 함수를 명시해주면 된다 ㅠㅠ 이게 꽤나 어려워서 외워야겠음

 

 

나의 풀이

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

struct compare{
    bool operator()(const vector<int>& a, const vector<int>& b){
        if(a[0]==b[0]) return a[1] > b[1];
        return a[0] > b[0]; // 시간순으로 들어온 내용 중에 점수 우선
    }
};

bool comp(vector<int> a, vector<int> b){
    if(a[1]==b[1]) return a[0] < b[0];
    return a[1] < b[1]; // 시간순 정렬
}

// 비선점, 우선순위=점수 낮은거부터
// 전체 종료시각, [점수]의 대기시간 sum
vector<long long> solution(vector<vector<int>> program) {
    sort(program.begin(), program.end(), comp); // 점수,시간,실행시간
    vector<long long> answer;
    long long waiting[10] = {0,};
    priority_queue<vector<int>, vector<vector<int>>, compare> pq;
    long long time = 0;
    int isRunning = 0;
    
    int index = 0;
    while(!pq.empty() || index < program.size() || isRunning>0){
        // 인덱스 범위 && 도착 시간이 되면 push
        while(index < program.size() && time >= program[index][1]){
            pq.push(program[index]);
            index++;
        }
        // 실행중인 프로그램이 없으면
        if(!pq.empty() && isRunning==0){
            vector<int> p = pq.top();
            pq.pop();
            isRunning = p[2];
            // 대기시간 = 시작 시간 - 도착 시간
            waiting[p[0]-1] += time - p[1];
        }
        time ++;
        if(isRunning>0) isRunning--;
    }
    answer.push_back(time);
    for(long long num: waiting) answer.push_back(num);
    return answer;
}