블로그

[C++] 1966 : 프린터 큐 본문

PS

[C++] 1966 : 프린터 큐

왕방토 2021. 3. 3. 17:08
728x90

실버 Ⅲ

 

#include <iostream>
#include <queue>
#include <utility>

using namespace std;

int main() {
	int T, N, M, tmp, idx, pri;

	scanf("%d", &T);
	while(T--) {

		queue <pair<int, int>> q;
		priority_queue <int> pq;

		int ans = 0;
		scanf("%d%d", &N, &M);

		for (int i = 0; i < N; i++) {
			scanf("%d", &tmp);
			q.push(make_pair(i, tmp));
			pq.push(tmp);
		}

		while (!q.empty()) {
			idx = q.front().first;
			pri = q.front().second;
			if (pri == pq.top()) {
				q.pop();
				ans++;
				pq.pop();
				if (idx == M) break;
			}
			else {
				q.push(q.front());
				q.pop();
			}
		}
		printf("%d\n", ans);
	}
}

 

 

"우선순위 큐"를 사용하는 문제 같아서

일부러 찾아서 사용했다 ->ㅋㅋㅋㅋㅋㅋ 열심이네 과거의 나 팟팅!!

 

근데 결국 우선순위 큐가 뭘 하는 건지 모르겠다

그냥 입력받음과 동시에 정렬해 주는 거 말고 하는 게 있나? -> 맞아요... 정렬해줘요..

+ 자료형이 큐라는 것? -> 음 큐..?? 큐긴한데 우선순위 큐인데..

오히려 큐라서 훨씬 사용하기 불편한데.. 원소 접근도 못하고

-> 그러니까 우선순위가 젤 높은 걸 그때 그때 필요로 하는 알고리즘에서 사용하면 좋겠지요?? 그래서 사실 우선순위가 젤 높은걸 그때 그때 꺼내는 로직이 아닌 문제라면 다 넣고 마지막에 정렬 한번만 해주는게 훨씬 빠르다

뭐가 좋다고 우선순위 큐를 쓸까?

몰겠다 -> ㅋㅋㅋㅋㅋㅋㅋ

아 그리고 찾아보니까 우선순위 큐

내림차순 정렬말고 오름차순 정렬도 할 수 있는 것 같다 -> 그럼 바로 배워서 여기다 써놨어야지! 약간의 게으름이 있네

'PS' 카테고리의 다른 글

[C++] 11444 : 피보나치 수 6  (0) 2022.01.08
[C++] 18111 : 마인크래프트  (0) 2021.03.04
[C++] 2447 : 별 찍기 - 10  (0) 2021.02.14
[C++] 2630 : 색종이 만들기  (0) 2021.02.14
[C++] 1629 : 곱셈  (0) 2021.02.13
Comments