[C++/우선순위 큐] 백준 1966 프린터 큐

1. 풀이

1. 큐 내 문서를 이동할 때 마다 인덱스가 변하므로 처음 입력받은 문서의 인덱스를 중요도와 함께 저장한다.(queue<pair<int,int>>) 현재 있는 문서들 중 중요도가 높은 것 부터 출력해야 하는데 큐 자료구조 상 먼저 넣은 것이 먼저 출력되므로 중요도를 역순으로 큐에 넣는다.(queue numbers). 중요도에 따른 카드수를 저장한다.(int cardNum[10])
2. 큐가 빌 때 까지 큐의 첫 원소를 꺼내서2) 그렇지 않은 경우 큐의 뒤에 다시 넣는다.
3. 1) 남은 카드들의 중요도 중 가장 높은 경우 카드 수와 중요도를 갱신
       +) 꺼낸 원소가 답일 경우 -> 결과를 리턴하며 종료한다

 

2. 코드

#include <iostream>
#include <queue>
using namespace std;
 
queue<pair<int,int>> q; // 중요도, 처음 인덱스
queue<int> numbers; // 카드 중요도 내림차순
int cardNum[10]; // 중요도별 카드 개수
 
int solve(int n, int m){
    int cnt = 1;
    while(!q.empty()){
        pair<int, int> now = q.front();
        q.pop();
        // 남은 카드 중 중요도 가장 높은 카드가 앞에 있는 경우
        if(now.first == numbers.front()){ 
            if(now.second == m) return cnt;
            cardNum[now.first]--;
            cnt++;
            if(cardNum[now.first] == 0) numbers.pop();
        }else{ // 앞카드 보다 중요도 높은 카드가 존재 할 경우
            q.push({now.first, now.second});
        }
    }
}
 
int main() {
    int t, n, m, num;
    cin >> t;
    while(t--){
        // 초기화
        q = queue<pair<int, int>>();
        numbers = queue<int>();
        fill(cardNum, cardNum + 10, 0);
 
        cin >> n >> m;
        for(int i = 0; i < n; i++){
            cin >> num;
            cardNum[num]++;
            q.push({num, i});
        }
 
        // 중요도에 따른 카드 수 갱신
        for(int i = 9; i >= 1; i--){
            if(cardNum[i] != 0) numbers.push(i);
        }
        cout << solve(n, m) << endl;
    }
    return 0;
}