백준 1966번 프린터 큐(C++)

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>

using namespace std;

int S, N, M;
int x;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> S;

	for (int i = 0; i < S; i++) {
		priority_queue<int> Q;
		queue<pair<int, int>> q;

		cin >> N >> M;

		int cnt = 0;

		for (int j = 0; j < N; j++) {
			cin >> x;
			Q.push(x);
			q.push(make_pair(j, x));
		}

		while (!q.empty()) {
			int index = q.front().first;
			int value = q.front().second;

			q.pop();

			if (Q.top() == value) {
				Q.pop();

				cnt++;

				if (M == index)
					break;
			}

			else q.push(make_pair(index, value));
		}

		cout << cnt << '\n';
	}
}

 

우선순위 큐 문제이다. 처음에는 priority_queue<int. int> 로 단순하게 구하려다가 실패하고 아이디어를 못 찾아 구글링해보니 두개의 큐를 구현하면 매우 쉽게 풀리는 문제였다. 

 

1. 우선순위 큐 pq = 우선순위들만 저장한다.

2. 일반 큐 q = 우선순위와 위치를 함께 저장한다.

3. pq.top() == q.front.우선순위 이면 pq.pop 으로 우선순위를 한칸 내린다. (프린트된 것이다.)

4. 그리고 입력한 알고싶은 위치값 까지 같다면 종료하고 카운트한 값을 출력, 아니면 다시 시작한다.

5. 3번에서 우선순위가 아니라면 일반 q 의 맨 뒤로 보낸다.

 

원래 네이버 블로그에서만 포스팅하다가 T스토리에도 시작했습니다. 둘다 병행하다가 더 좋은곳에 정착할듯..?