BOJ (C/C++) 1966번: 프린터 큐

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

1966번: 프린터 큐

---

풀이

큐에서는 원소의 탐색이 어려워서 큐와 똑같이 동작하는 벡터를 사용하여 최댓값을 찾아냄.

---

코드

#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;

vector <int> V;
queue <pair<int, int>> Q;

int Find_max(int N) {
	int max = 1, max_i = 0;
	for (int i = 0; i < N; i++) {
		if (max < V[i]) max = V[i], max_i = i;
	}

	V[max_i] = 0; // 큐에선 제거된 원소
	return max;
}
int main() {
	int T, N, M;
	int n, idx, max, cnt = 0;
	scanf("%d", &T);
	for (int t = 0; t < T; t++) {
    
		scanf("%d %d", &N, &M);
		for (int i = 0; i < N; i++) {
			scanf("%d", &n);
			V.push_back(n);
			Q.push({ i,n });
		}
		
		while (1) {
			max = Find_max(N);
			while (1) {
				idx = Q.front().first, n = Q.front().second;
				if (n == max) break;

				// 중요도가 가장 높은 문서가 가장 앞에 올 때까지
				Q.push({ idx,n });
				Q.pop();
				int tmp = V[0]; V[0] = V[N - 1]; V[N - 1] = tmp;
			}
			cnt++;
			if (idx == M) break;
			Q.pop();
		}
		printf("%d\n", cnt);

		// 초기화
		cnt = 0;
		V.clear();	
		while (!Q.empty()) Q.pop();
	}
	return 0;
}