알고리즘/백준
[C++/우선순위 큐] 백준 1966 프린터 큐
waterground
2019. 12. 22. 11:17
1. 풀이
- 큐 내 문서를 이동할 때 마다 인덱스가 변하므로 처음 입력받은 문서의 인덱스를 중요도와 함께 저장한다.(queue<pair<int,int>>) 현재 있는 문서들 중 중요도가 높은 것 부터 출력해야 하는데 큐 자료구조 상 먼저 넣은 것이 먼저 출력되므로 중요도를 역순으로 큐에 넣는다.(queue numbers). 중요도에 따른 카드수를 저장한다.(int cardNum[10])
- 큐가 빌 때 까지 큐의 첫 원소를 꺼내서2) 그렇지 않은 경우 큐의 뒤에 다시 넣는다.
- 1) 남은 카드들의 중요도 중 가장 높은 경우 카드 수와 중요도를 갱신
+) 꺼낸 원소가 답일 경우 -> 결과를 리턴하며 종료한다
2. 코드
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
|
#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;
}
|
cs |