[백준] 1966: 프린터큐

프린터큐가 날 눈물짓게 해...

생각보다 구현이 사나워서 해답을 찾아보니 priority queue를 사용한 풀이가 나왔다.

그런데 생각보다 priority queue로 해결하는 것이 아닌, queue, priority queue를 2개 다 쓰길래

그냥 queue, vector로 구현했다.

원래는 priority queue에서 pair로 받아서 compare하는 부분을 정의해서 queue하나로 다 완성하고 싶었는데

우선 compare부분을 내가 정의하려고 하는것에서 실패했고,

출력순서를 신경써야 하기 때문에 한 큐에 해결이 불가능하긴 했다.

 

priority_queue 쓰는거랑, vector에 저장해서 sort 하는거랑 큰 차이가 있는지는 모르겠다. (둘 중에 뭐가 더 빠를까?)

 

내가 짠 코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

bool comp(int a, int b){
    return a>b;
}
int main(void){
    int T,N,O;
    int i,j,value;
    int idx,prior;

    scanf("%d",&T);
    
    for(i=0;i<T;i++){
        scanf("%d %d",&N,&O);
        vector <int > v;
        queue <pair <int, int > > q;
        for(j=0;j<N;j++){
            scanf("%d",&value);
            q.push(make_pair(j,value));
            v.push_back(value);
        }
        sort(v.begin(),v.end(),comp);
       
        for(j=0;j<N;j++){
            while(q.front().second != v[j]){
                idx = q.front().first;
                prior = q.front().second;
                q.pop();
                q.push(make_pair(idx,prior));
            }

            if(q.front().first==O) {
                printf("%d\n",j+1);
                break;
            }

            q.pop();
        }
    }
    return 0;
}

www.acmicpc.net/problem/1966

1966번: 프린터 큐