[백준/C++] 1966번 프린터 큐

1.문제 링크

1966

2. 풀이 전 계획과 생각

• 자료구조 큐 이용하기

3. 풀이

#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;

bool cmp(int i, int j){
	if(i>j) return true;
	else return false;
}

int main(){
    int t; cin>>t;
    
    while(t--){
        queue<pair<int,int> > q;
        vector<int> v;
        int n,m; cin>>n>>m;
        // input
        for(int i=0;i<n;i++){
            int temp; cin>>temp;
            v.push_back(temp);
            if(i==m){
                q.push({temp,1});
            }
            else q.push({temp,0});
        }
        
        // sort
        sort(v.begin(), v.end(), cmp);
        
        int printIndex=0;
        int cnt=0;
        while(true){
            if(q.front().first==v[printIndex]){
                if(q.front().second==1){
                	cnt++;
                    cout<<cnt<<'\n';
                    break;
                }
                else{
                    q.pop();
                    printIndex++;
                    cnt++;
                }
            }
            else{
                q.push(q.front());
                q.pop();
            }
        }
    }
}

1. 입력을 받을 때 q에 {중요도,추적여부}를 저장한다. 즉 큐에는 입력받는 중요도와 만약 몇번째로 인쇄되는지 원하는 문서의 경우 1을 아닌경우는 0으로 저장한다. 함께 v벡터에 중요도를 저장한다.

2. 중요도만 저장되있는 v벡터를 내림차순 정렬한다.

3. printIndex=0으로 초기화하고 인쇄될 때마다 1씩 증가한다. while반복문에서 큐의 첫번째 원소의 중요도와 내림차순 정렬된 v벡터의 printIndex 위치의 값이 일치하면서 큐의 second가 1인경우 값을 출력하고 빠져나오기.

4. 아니라면 큐의 맨 앞 원소를 마지막에 push하고, 맨 앞 원소를 pop하기

4. 풀이하면서 고민했던 점

• 없음

5. 문제를 풀고 알게된 개념 및 소감

• 자료구조 큐에 대한 이해가 올라감.