[백준 BOJ 1966 silver3 - 프린터 큐] 자료구조 , 큐 C++

백준 프린터 큐

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

1966번: 프린터 큐

 

현재 큐에 문서들이 주어졌을 때, 앞에서부터 문서를 출력한다.

단, 나머지 문서들 중에 front보다 중요도가 더 큰 문서가 있다면, 출력하지 않고 큐의 뒤로 보낸다.

 

일단 큐에 문서들을 차례로 집어넣고, 앞에서부터 확인을 해야한다.

나머지 문서들과 중요도를 어떻게 비교할까 하다가 우선순위 큐를 함께 사용했다.

 

우선순위 큐에 주어진 문서를 다 넣으면, 중요도가 큰 문서가 앞으로 오도록 정렬된다. 즉 우선순위 큐를 통해 현재 출력해야 하는 문서를 알 수 있다. 

 

1. 큐의 front 중요도와 우선순위 큐의 top 과 같다면, 현재 문서들 중 front보다 중요도가 큰 문서는 없으므로 출력한다.

2. 다르다면 큐의 front를 pop하고 뒤에 push한다. 

 

int save_order[100];
int T, N, idx;

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

	cin >> T;
	int doc;
	for (int i = 0; i < T; i++) {
		queue <pair<int, int>> q;
		priority_queue <int> pq;
		memset(save_order,0,sizeof(save_order));

		cin >> N >> idx;
		for (int j = 0; j < N; j++) {
			cin >> doc;
			q.push({ doc,j });
			pq.push(doc);
		}

		int order = 1;
		while (!q.empty()) {
			int front = q.front().first;
			int qidx = q.front().second;
			int pq_front = pq.top();

			if (front == pq_front) {
				q.pop();
				pq.pop();
				save_order[qidx] = order; //출력 순서 저장
				order++;
			}
			else {
				q.pop();
				q.push({ front, qidx });
			}
		}
		cout << save_order[idx] << "\n";
	}
}