[백준(BOJ)/C++] 1966번: 프린터 큐 - 코딩밥상

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

1966번: 프린터 큐

 

접근방법

처음엔 단순히 파일이 들어오는 순서대로 인덱스값과 우선순위 값을 pair로 저장하여 큐에 넣어주고

큐의 front값의 우선순위값과 비교하여 더 높은 우선순위가 등장하면 큐에 다시 넣어주고 우선순위가 더 높은 파일이 없는 경우에 큐에서 빼주는 식으로 코드를 짰다

(오답 코드)

틀린 풀이

하지만 이렇게 되면 우선순위값이 동일한 경우에는 순서가 바뀌게 된다.

이렇게 한참을 어디에서 틀렸는지 고민하다가 디버깅을 해보면서 깨달았고,

그 때 생각난 자료구조가 바로 우선순위 큐이다.

이걸 모르고 문제를 풀려다 보니 한참을 걸리지 어휴...

 

여기서 우선순위 큐란 간단하게 설명하면, 어떤 원소가 push되면 주어진 우선순이에 맞춰서 Queue가 O(logN)만에 정렬되고, pop은 정렬된 Queue의 앞에서 이루어진다. (우선순위 큐의 자세한 부분은 나중에 자료구조 포스팅에서 다루겠습니다.)

 

틀린 코드에서 우선순위 큐를 따로 만들어주면 파일이 우선순위대로 정렬된 상태에서 비교할 수 있게되면서 쉽고 빠르게 알고리즘을 짤 수 있게된다. 다시 한번 자료구조의 힘을 알 수 있었다.

 

올바른 코드

#include <iostream>
#include <stdlib.h>
#include <queue>
using namespace std;

int main(){
    int t;
    cin>>t;
    
    int n,m;
    for(int i=0; i<t; i++){
        cin>>n>>m;
        queue<pair<int, int>> q;
        priority_queue<int> pq;
        
        for(int j=0; j<n; j++){
            int pri;
            cin>>pri;
            q.push({j, pri});
            pq.push(pri);
        }
        
        int count = 0;
        while(!q.empty()){
            pair cmp = q.front();
            q.pop();
            
            if(cmp.second < pq.top()){   //큐에 우선순위가 더 높은 파일이 있을 경우 cmp를 후번 순서로 다시 넣는다
                q.push(cmp);
            }
            else{   //큐에 우선순위가 더 높은 파일이 없는 경우 카운트 업, 찾는 인덱스와 비교 후 동일하면 중지
                count++;
                pq.pop();
                if(cmp.first == m) break;
            }
        }
        cout<<count<<'\n';
    }
}

 

우선순위에는 파일들의 중요도 정보를 넣어주고, 정렬된 중요도와 큐에 들어가 있는 파일들 중 front값과 비교를 해주면

중요도가 큰 파일의 유무를 바로 알 수 있게 된다.

만약 큐의 front파일이 중요도가 가장 높은 파일일 경우 출력하고 그렇지 않다면 다시 큐의 끝에 넣어주면 된다.