[1966] 프린터 큐

---

https://www.acmicpc.net/problem/1966

1966번: 프린터 큐

큐 문제이다.

 

내가 알고싶어하는 문서가 queue의 몇 번째에 들어가있는지, 그리고 이것을 따져가며 출력을 해야했기에 살짝 까다로웠다.

 

일단 queue를 생성해야 한다.

내가 원하는 문서의 queue 순서를 표시해줘야하기 때문에 queue를 구조체로 생성하였다.

struct mymy {
	int idx; 
	bool isCheck = false;
};

queue<mymy> myqueue;

isCheck이 true라면 내가 원하는 문서라는 뜻이다..

 

내가 원하는 문서가 출력되는 순서를 알고싶으면 어떻게 해야될까?

일단 인쇄될 때마다 맨 앞에 있는 문서가 제일 높은 중요도인지/아닌지를 판별해야 한다.

그것에 따라서 인쇄할지/뒤로 재배치할지 이벤트를 처리해야하기 때문이다.

 

난 중요도를 담는 배열을 생성해서 내림차순 정렬을 하였고, 항상 A[0]가 현재 인쇄되지 않은 문서들 중에서 제일 큰 중요도인 것을 활용하여 이벤트를 처리했다.

중요도가 큰 것이 뒤에 있다고 확인되면 queue의 가장 뒤에 재배치하고,

제일 앞에 나와있는 문서가 중요도가 제일 크면 인쇄한다.

 

이 때 내가 궁금해하던 문서라면 순서를 출력 후 while문을 종료,

궁금해하던게 아니면 인쇄(pop)를 해주며 while문을 진행한다.

 

자세한 건 코드로!

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

struct mymy {
	int idx; 
	bool isCheck = false;
};

int K; int A[100]; // 중요도 내림차순 정렬에 필요한 배열

bool cmp(int a, int b) { // 내림차순
	return a > b;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> K;

	for (int i = 0; i < K; i++)
	{
		int N, M; queue<mymy> myqueue;
		cin >> N >> M;

		// queue 생성
		for (int j = 0; j < N; j++)
		{
			int tmp; cin >> tmp;
			if (j == M) { 
				// 내가 궁금한 queue 순서라면
				// isCheck를 true로
				myqueue.push({ tmp, true }); 
			} 
			else myqueue.push({ tmp, false });
			A[j] = tmp; // 중요도를 배열에도 담음
		}

		// 순서 출력
		int order = 1;
		while (1) {
			sort(A, A + N, cmp); // 내림차순 정렬
			int maximum = A[0]; // 지금 제일 큰 중요도
			mymy tmp; tmp = myqueue.front();
			if (tmp.idx < maximum) {
				// 하나라도 중요도 큰 게 뒤에 있다면
				// queue의 가장 뒤에 재배치
				myqueue.pop(); myqueue.push(tmp); 				
			}
			else {
				// 내가 제일 크면
				if (tmp.isCheck) {
					// 내가 궁금해하던 순서라면
					// 순서 출력 후 바로 종료
					cout << order << "\n";
					break;
		  		}
				else {
					// 내가 궁금해하던게 아니면
					// 인쇄 (pop)
					myqueue.pop();
					N--; // 인쇄될 때마다 문서의 개수가 하나씩 줄어드므로
					A[0] = 0; // 1-9이므로 0으로 설정하여 없는 중요도 취급
					order++; // 순서 증가
				}
			}
		}
	}
}