큐 - 백준 1966번 프린터 큐

www.acmicpc.net/problem/1966

1966번: 프린터 큐

벌써 3번째 푸는 문제다. 자료구조 스터디때 한 번, 프로그래머스 고득점 킷에서 한 번 휴ㅠ

프로그래머스 문제는 여기서 확인 가능 👉 blahblahlab.tistory.com/40

 

IDEA

중요도를 importance 라는 벡터에 저장한 후, 내림차순으로 정렬한다.

그 후 que에 중요도와 인덱스를 함께 push 해준다.

que의 front를 아래 3가지에 해당하는지 확인해본다.

 

1. front 값의 중요도가 현재 가장 큰 중요도와 같으며 내가 찾던 인덱스번호와 같다.

내가 찾고자하던 문서의 출력순서를 알아냈기떄문에 더 이상의 작업은 불필요하다.

출력될 때마다 idx 가 늘어났으므로 출력순서와 idx는 같을 것이다. 

정확하게 말하면 출력순서는 1부터고 idx 는 0부터이므로 출력순서 = idx +1 이다. 

이후 break를 통해 반복문을 끝내버린다. 

 

2.  front 값의 중요도가 현재 가장 큰 중요도와 같으며 내가 찾던 인덱스번호와 다르다.

현재 가장 큰 중요도와 같으면 출력해줘야하므로 우선 pop해줘야한다. 그리고 하나 더 출력했으니까 idx도 하나 더해준다.  idx를 더해주면 다음 중요도로 바뀐다. 하지만 내가 찾던 번호가 아니라 작업을 이어가야한다. 

 

3. front가 현재 가장 큰 중요도가 아닐 경우 

출력을 할 수 없으니 뒤로 push 해주자. 이 경우 출력이 되지 않았으므로 idx를 하나 더 늘려주지 않는다. 

현재 가장 큰 중요도가 바뀐 게 아니니 유지해주어야한다. 

 

CODE

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

int main() {
	int tc;
	scanf("%d", &tc);
	for (int t = 0; t < tc; t++) {
		queue<pair<int, int>>q; //importance , index
		vector<int>importance;
		// 준비
		int n, k;
		scanf("%d %d", &n, &k);
		for (int i = 0; i < n; i++) {
			int impt;
			scanf("%d", &impt);
			importance.push_back(impt);
			q.push({ impt , i });
		}
		sort(importance.begin(), importance.end(), greater<int>());
		int idx = 0;
		while (1) {
			if (q.front().first == importance[idx]) {
				if (q.front().second == k) {
					printf("%d\n", idx+1);
					break;
				}
				else {
					q. pop();
					idx++;
				}
			}
			else {
				int impt = q.front().first;
				int index = q.front().second;
				q.pop();
				q.push({ impt , index });
			}
		}
	}
}