프린터 큐 - 실버3(1966)

작성일 | In

문제

image

링크

문제 해결

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<iostream>  
#include<algorithm>  
#include<queue>  
  
using namespace std;  
  
int testNum, N, M;  
int countVal;  
  
void solution() {  
    int ipt;  
    queue <pair<int, int>> q;  
    priority_queue<int> pq;  
    for (int i = 0; i < N; i++) {  
        cin >> ipt;  
        pq.push(ipt);  
        q.push({i, ipt});  
    }  
    while (!q.empty()) {  
        int index = q.front().first;  
        int iptValue = q.front().second;  
        q.pop();  
        if (pq.top() == iptValue) {  
            pq.pop();  
            countVal++;  
            if (index == M) {  
                cout << countVal << "\n";  
                break;  
            }  
        } else {  
            q.push({index, iptValue});  
        }  
    }  
}  
  
void input() {  
    cin >> testNum;  
    for (int i = 0; i < testNum; i++) {  
        cin >> N >> M;  
        countVal = 0;  
        solution();  
    }  
}  
  
void solve() {  
    input();  
}  
  
int main() {  
    ios::sync_with_stdio(false);  
    cin.tie(nullptr);  
    cout.tie(nullptr);  
  
    solve();  
    return 0;  
}
  • 우선순위 큐에 우선순위를 넣으면 자동으로 내림차순 정렬(큰 -> 작)이 된다. 현재 queue에 우선순위가 우선순위 큐에 제일 앞의 값(우선순위 큰 값)과 같다면(== 현재 queue가 가장 우선순위가 크다) 우선순위 큐값 하나를 제거해주고 만약 현재 인덱스가 찾고자하는 문서인지 체크 후 몇번째 인쇄가 되었는지 출력을 한다.