프로그래머스 프린터 (c++)

https://programmers.co.kr/learn/courses/30/lessons/42587

코딩테스트 연습 - 프린터 | 프로그래머스

먼저 큐에 인쇄 대기목록을 모두 넣어주고 우선순위 큐를 하나 더 만들어서 중요도를 모두 넣어준다.

우선순위 큐는 기본적으로 최대 힙이기때문에 큰 값이 먼저 나온다.

 

이제 큐에 넣은 인쇄 대기목록을 순차적으로 처리해줄건데

먼저 중요도가 가장 높아야 하고 그 다음에는 순차적으로 앞에 있는 문서를 인쇄하면 된다.

 

먼저 큐에 있는 값을 뽑아와서 pop한 후에

우선순위 큐의 top에 있는 값과 현재 문서의 중요도가 같다면 인쇄하면 된다.

현재 우선순위가 사용되었으므로 우선순위 큐도 pop해주고 인쇄를 한 번 했으므로 answer도 1 증가시킨다.

이때 만약 인쇄한 문서가 내가 요청한 문서라면(location) 더 이상 인쇄를 할 필요가 없으므로 break해준다.

 

우선순위 큐의 top에 있는 값과 문서의 중요도가 같지 않았다면

현재 문서보다 중요도가 더 높은 문서가 존재한다는 뜻이므로 인쇄를 하지 않고 다시 큐에 넣어준다.

 

#include <string>
#include <vector>
#include <queue>
 
using namespace std;
 
 
int solution(vector<int> priorities, int location) {
    int answer = 0;
    priority_queue<int> pq;
    queue<pair<int,int>> q;
    
    int size = priorities.size();
    for(int i=0; i<size; i++) {
        q.push(make_pair(i, priorities[i]));
        pq.push(priorities[i]);
    }
    
    
    while(!q.empty()) {
        int i = q.front().first;
        int p = q.front().second;
        q.pop();
        
        //현재 문서의 중요도가 가장 높은 중요도라면 인쇄
        if(p == pq.top()) {
            pq.pop();
            answer += 1;
            
            //현재 문서가 내가 인쇄를 요청한 문서다
            if(i == location) {
                break;
            }
            
        } else {
            //다시 큐에 넣는다.
            q.push(make_pair(i,p));
        }
 
    }
    
    return answer;
}