C++ / 백준 / 1966 / 프린터 큐

문제

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

1966번: 프린터 큐

문제풀이

pair<int, int>형태를 가진 큐를 선언(first는 해당 문서가 몇 번째인지, second는 해당 문서의 우선순위를 나타낸다).

벡터 priority로 문서들의 우선순위 값을 내림차순으로 나타낸다.

각각의 값들을 입력받고 sort를 해서 벡터를 내림차순으로 정렬한다.

while문을 통해 문서 M을 출력할 때까지 반복을 한다.

큐의 front 값이 우선순위가 제일 높은지, 높다면 문서 M인지, 문서 M이 아니라면  pop을 하고

현재 큐에 남은 우선순위 중 가장 높은 값의 위치를 나타내는 idx값을 1 늘린다.

우선순위가 높지 않다면 front값을 큐에 push 하고 pop을 한다(위치만 앞에서 끝으로 옮긴다).

 

 

코드

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

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

	int T(0), N(0), M(0);
	cin >> T;
	int num(0), idx(0);

	while (T--) {
		cin >> N >> M;
		vector<int>priority(N, 0);
		queue<pair<int, int>>q;

		for (idx = 0; idx < N; ++idx) {
			cin >> priority[idx];
			q.push({ idx,priority[idx] });
		}

		sort(priority.begin(), priority.end(), greater<>());

		idx = 0;

		while (1) {
			if (q.front().second == priority[idx]) {
				if (q.front().first == M) {
					cout << idx + 1 << '\n';
					break;
				}
				else {
					q.pop();
					++idx;
				}
			}
			else {
				q.push({ q.front().first,q.front().second });
				q.pop();
			}
		}
	}
}