[BOJ] 1966 - Printer Queue

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

---

[알고리즘풀이]

이름부터 Queue를 이용하는 문제다.

Queue에 있는 중요도 중 가장 큰 값을 찾고,

Queue의 가장 앞에 있는 문서의 중요도가 가장 큰 값과 같다면 Pop을 하고, 아니면 뒤로 Push한다.

이때, Queue의 가장 앞에 있는 문서의 중요도가 가장 크면서, 내가 찾는 문서라면 알고리즘을 종료하며

지금까지 Pop이 일어난 횟수(나보다 앞에서 나간 문서의 수)를 출력해주면 된다.

#include<iostream>
#include<queue>

using namespace std;

int main(void) {
	int t;
	cin >> t;
	while (t--) {
		queue<int> q;
		int n, m;
		cin >> n >> m;
		for (int i = 0; i < n; i++) {
			int x;
			cin >> x;
			q.push(x);
		}
		bool flag = true;
		int count = 1, max;
		while (1) {
			if(flag){
				max = 0;
				for (int i = 0; i < q.size(); i++) {
					if (max < q.front())
						max = q.front();
					q.push(q.front());
					q.pop();
				}
			}
			if (m == 0 && q.front() == max) {
				cout << count << '\n';
				break;
			}
			else if (m == 0 && q.front() != max) {
				m = q.size() - 1;
				q.push(q.front());
				q.pop();
				flag = false;
			}
			else if (q.front() == max) {
				count++;
				q.pop();
				m--;
				flag = true;
			}
			else {
				q.push(q.front());
				q.pop();
				m--;
				flag = false;
			}
		}
	}

}

[주의할점]

queue에서 max 값을 찾기 위해서는 queue를 순회하며 pop, push를 진행해야 된다.

즉, max 값을 찾는 행위 자체가 시간을 많이 잡아먹는다.

따라서, max가 변하지 않는 경우에는 max 값을 찾는 행위를 하지 않으며 시간을 줄여야 된다.

---