#1966 프린터 큐(C++)

https://www.acmicpc.net/problem/1966

 

1966번: 프린터 큐

 

처음에 덱과 큐를 이용해서 푼 방식

#include <iostream>
#include <string>
#include <queue>
#include <deque>

using namespace std;

int main()
{
    int n;
    cin >> n;
    while(n--){
        deque<queue<int>> dq;
        //vector<int> v;
        int k, m;
        cin>>k>>m;
        for(int i=0; i<k ; i++){
            queue<int> sub_q;
            int priority;
            cin>>priority;
            sub_q.push(i);
            sub_q.push(priority);
            dq.push_back(sub_q);// 각각 원래순서(0부터~), 중요도 순서(큰 순서)
        }

        //나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 
        //이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 
        //그렇지 않다면 바로 인쇄를 한다.
        while(!dq.empty()){    
            for(int i=1; i<dq.size() ; i++){
                if(dq[0].back() < dq[i].back()){
                    dq.push_back(dq.front());
                    dq.pop_front();
                    i=0;
                }
            }
            if(dq.front().front()==m){
                cout<<k-dq.size()+1<<endl;
                break;
            }
            else
                dq.pop_front();
        }

    }
}

다른 분들을 보니 전부 우선순위로 풀었길래 급히 코드를 수정해야겠다고 생각했다.

 

우선순위 큐를 볼 때마다 이런게 있구나~ 했다가 금세 잊어버렸는데, 이번 기회에 추후에도 활용할 수 있도록 잘 정리 해야겠다.

 

우선순위 큐(Priority Queue)

높은 우선순위를 가진 원소는 낮은 우선순위를 가진 원소보다 먼저 처리된다.

우선순위 큐는 "리스트"나 "맵"과 같이 추상적인 개념이다; 마치 리스트는 연결 리스트나 배열로 구현될 수 있는 것과 같이, 우선순위 큐는 힙이나 다양한 다른 방법을 이용해 구현될 수 있다.

- <queue> 헤더에 있다.

- priority_queue<자료형> 변수 이름;

 

- pq.push(원소); // 제일 뒤에 원소를 넣음, 내부적으로 정렬됨

- pq.pop(); // 제일 앞 원소를 삭제

- pq.top(); // 제일 앞 원소 반환

 

- pq.empty() // 우선순위 큐가 비어있는지? 비어있으면 true, 뭔가 있으면 false 반환

- pq.size() // 길이 반환

 

 

이 우선순위 큐를 이용해서 다시 코드를 짜 봤다.

#include <iostream>
#include <string>
#include <queue>
#include <utility>

using namespace std;

int main()
{
    int n;
    cin >> n;
    while(n--){
        queue<pair<int,int>> q;
        priority_queue<int> pq;
        //vector<int> v;
        int k, m;
        cin>>k>>m;
        for(int i=0; i<k ; i++){
            int priority;
            cin>>priority;
            q.push(make_pair(i,priority));// 각각 원래순서(0부터~), 중요도 순서(큰 순서)
            pq.push(priority);
        }

        while(!q.empty()){
            while(q.front().second != pq.top()){
                if(q.front().second < pq.top()){
                    q.push(q.front());
                    q.pop();
                }
            }
            if(q.front().first==m){
                cout<<k-q.size()+1<<endl;
                break;
            }
            q.pop();
            pq.pop();
        }

    }
}

- 내가 기존에 했던 while문 내부(정렬하는 부분)을 우선순위 큐를 활용하여 코드를 변경했다.

    - 우선순위 큐의 맨 앞과 같을 때까지 계속 맨 앞 원소를 뒤로 보내는 작업을 반복했다.

- 우선순위 큐를 이용해서 비교하게 되면 큐의 중간 부분을 비교하지 않아도 되므로 deque 대신 그냥 queue를 사용하였다.

- 이중 큐 대신 큐 내에 pair를 사용하였다.

 

 

 

참고-

https://ko.wikipedia.org/wiki/%EC%9A%B0%EC%84%A0%EC%88%9C%EC%9C%84_%ED%81%90

우선순위 큐 - 위키백과, 우리 모두의 백과사전