PCCP 모의고사 1] 4번 운영체제 c++ (우선순위 큐)

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

프로그래머스

 

문제 해설

우선, 아무 생각 없이 우선순위, 실행 시간, 입력 들어온 순서, 실행 순서  가 낮은 순으로 우선순위 큐에 넣고 그대로 pop()해가며 답을 구하면 될 줄 알았지만, 이렇게는 해결할 수 없다.( 만약 첫 프로그램이 5초에 종료 되었는데, 가장 우선순위가 높은 프로그램이 8초에 시작한다고 5~8초에 아무도 실행하지 않는 반례가 발생한다.) 

즉, 프로그램의 priority가 높고, 실행 시간이 빠른 순으로 수행할 경우, 현재 시간이 아직 '시작 시간' 에 도달하지 못한 경우 뒤로 밀리는 경우의 수가 생기는 것이다. 

그래서 각 우선순위 (1~10) 을 가진 프로그램을 각기 다른 10개의 우선순위 큐에 넣은 뒤, 그들을 "시작 시간"이 빠른 순으로 pop()하도록 '<' 연산자를 제정의 했다. 이후 시작, 종료 시간에 따라 적절히 구현하면 문제가 해결된다.

 

정답 코드

#include <string>
#include <vector>
#include<queue>
using namespace std;
struct prog{
    int st;
    int len;
    int n;
    int p;
    
    bool operator<(prog other) const {
        if(st!=other.st) return st>other.st;
        if(n!=other.n) return n>other.n;
        return len>other.len;
    }
    
};



vector<long long> solution(vector<vector<int>> program) {
    vector<long long> answer(11,0);
    priority_queue<prog> pq[11];// 1~10 우선 순위 프로그램들을 시작시간으로 정렬
    
    for(int i=0;i<program.size();i++){   
        pq[program[i][0]].push({program[i][1],program[i][2],i,program[i][0]});
    }
    int time=0;

    while(1){
        prog now;
        prog fast;
        bool find=false;
        int min=987654321. cnt=0,fast_i=0;
        for(int i=1;i<=10;i++){//우선 순위가 높은 순으로 탐색
            if(pq[i].empty()){
                cnt++;
                continue;
            }
            prog tmp=pq[i].top();
            if(tmp.st<=time){ // 현재 시간에 만족하는 프로그램 을 실행 
                now=pq[i].top();
                pq[i].pop();
                find=true;
                break;
            }
            if(min>tmp.st){ //전체 프로그램 중 가장 빠른 실행 시간인 프로그램 저장
                fast_i=i;
                min=tmp.st;
            }
        }
        if(cnt==10) break; //모든  pq가 비었기에 종류
        if(!find){ // 현재 time에 수행 가능한 프로그램이 없다면 
            now=pq[fast_i].top();//가장 빨리 시작되는 프로그램 실행
            pq[fast_i].pop();
            time=now.st;
        }

        answer[now.p]+=(time-now.st);//대기시간 추가
        time+=now.len;
    }
    answer[0]=time;
    return answer;
}

 

 

 

+@ 시간초과 코드

단순하게 매번 우선순위(1~10 의 우선순위 값)이 높은 프로그램을 pop하고, 만약 아직 실행시간이 안되었다면 마지막에 다시 push 하는 방식의 구현도 했지만, 당연히 불필요한 연산들로 인해 시간초과가 발생했다..

#include <string>
#include <vector>
#include<queue>
using namespace std;
struct prog{
    int p;
    int st;
    int len;
    int n;
    
    bool operator<(prog other) const {
        if(p!=other.p) return p>other.p;
        if(st!=other.st) return st>other.st;
        if(n!=other.n) return n>other.n;
        return len>other.len;
    }
    
};



vector<long long> solution(vector<vector<int>> program) {
    vector<long long> answer(11,0);
    priority_queue<prog> pq;//우선순위, 실행 시간, 종료시간,순서

    // struct program p1={1,2,3,4};
    // printf("%d",p1.ed);
    for(int i=0;i<program.size();i++){
        pq.push({program[i][0],program[i][1],program[i][2],i});
    }
    int time=0;
    
    //time이 그새 지나면..?
    while(!pq.empty()){
        vector<prog> tmp;
        while(time<pq.top().st){
            tmp.push_back(pq.top());
            pq.pop();
        }
        prog now=pq.top();
        pq.pop();
        for(auto a:tmp){
            pq.push(a);
        }
        if(time>now.st){ //대기시간 존재.
            answer[now.p]+=(time-now.st);//대기시간 추가
        }
        time+=now.len;
        
    }
    answer[0]=time;
   
    

    return answer;
}