(매일 BOJ) C++ 1966번 프린터 큐

이번 문제는 실버 3 난이도의 프린터 큐 문제이다.

접근법

문서가 몇번째로 인쇄되는지를 알기 위해서 queue에 index과 value 를 동시에 수용한 후 내림차순으로 정렬해주는 priority_queue 를 사용하여 value가 priority_queue의 값과 같으면 pq를 pop() 하고 아니라면 index과 value를 queue에 push 하는 방식으로 구현하였다.

 

새롭게 배운 내용 - priority_queue

 

우선순위를 기준으로 가장 중요한 값이 먼저 나오는 자료구조

• 일반 큐는 먼저 들어온 게 먼저 나감 (FIFO).
• 우선순위 큐는 가장 우선순위 높은 값이 먼저 나감 (값 기준 정렬됨).
• 내부적으로 힙(heap) 자료구조로 구현돼 있음 (기본: max heap)

예시코드

#include <queue>
priority_queue<int> pq;
pq.push(3);
pq.push(1);
pq.push(5);
cout << pq.top();  // 출력: 5 (가장 큰 값)

 

• 내림차순 정렬된 상태로 가장 큰 값이 항상 top()에 위치함.
• pop()하면 가장 큰 값부터 빠짐.

priority_queue 함수

pq.push(x)	x를 큐에 넣음
pq.top()	가장 우선순위 높은 값 확인 (삭제 X)
pq.pop()	가장 우선순위 높은 값 꺼냄 (삭제 O)
pq.empty()	비어있는지 확인
pq.size()	큐의 크기

 

 

아래는 작성한 코드이다.

# include <bits/stdc++.h>
using namespace std;

int main (void){
    ios::sync_with_stdio(0); cin.tie(0);
    int N;
    cin >> N;
    for (int i = 0; i < N; i++){
        queue<pair<int,int>> q;
        priority_queue<int> pq; // 내림차순 정렬되는 queue
        int n,m;
        cin >> n >> m;
        for (int j = 0; j < n; j++){
            int num;
            cin >> num;     
            q.push({j,num});
            pq.push(num);
        }

        int count = 0;
        while (1){
            int index = q.front().first;
            int value = q.front().second;
            q.pop();
            if (pq.top() == value){
                pq.pop();
                count += 1;
                if(index == m){
                    cout << count << '\n';
                    break;
                }
            }
            else{
                q.push({index,value});
            }
        }
    }
}