1주차(자료구조) - [C++]백준1966 프린터 큐

09 Mar 2022 in Study on Algorithm

백준1966 프린터 큐 링크

문제

예제 입력

---

코드

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

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); 

	int cycle;
	cin >> cycle;

	for (int i = 0; i < cycle; i++) {
		int N, M, num, cnt = 0;
		queue<pair<int, int>> Queue;
		priority_queue<int> temp;
		cin >> N >> M;
		for (int j = 0; j < N; j++) {
			cin >> num;
			Queue.push({ num, j });
			temp.push(num);
		}

		while (true)
		{
			int priority = Queue.front().first;
			int val = Queue.front().second;

			if (temp.top() == priority) {
				temp.pop();
				cnt++;
				if (val == M)
					break;
			}
			else {
				Queue.push({ priority, val });
			}
			Queue.pop();
		}
		cout << cnt << "\n";
	}
}

설명

C++ STL(표준 템플릿 라이브러리)에서 큐와 우선수위 큐를 사용하여 큐에는 순서를 원형큐로 관리하며 우선순위 큐는 정해준 우선순위 중 가장 높은것을 확인하고 큐에 순서가 맞다면 cnt(카운트)를 해주며 원하는 순서가 왔을때 break문으로 벗어납니다.

-pair<자료형, 자료형> 변수명; : 하나의 변수에 2가지 값을 저장함

<queue>
-queue<자료형> 변수명; : 큐 자료구조 사용
-priority_queue<자료형, 자료형태, 비교함수> 변수명; : 우선순위 큐(힙) 자료구조 사용

<비교함수>
-greater<자료형> : 내림차순 정렬
-less<자료형> : 오름차순 정렬

---

결과