[백준]Baekjoon1966(Queue)

위의 문제를 해결하기 위해서 나는 priority_queue(우선순위 큐)와 queue를 동시에 사용했다.

priority_queue를 사용하면 가장 기본적인 포맷으로 사용했을 때 저절로 내림차순으로 큐안에서 정렬이 된다.

그래서 queue에서 가장 큰 수를 찾기위해서 priority_queue를 따로 사용하였다.

또한 queue에는 두개의 값을 동시에 넣는 pair를 이용해 문서의 위치와 문서의 중요도를 동시에 삽입하였다.

priority_queue를 이용해 큐에서 가장 큰 값을 찾고 queue의 가장 앞에 있는 값과 비교를 하면서 문제를 풀어나갔다.

자세한 것은 아래의 코드와 주석을 통해서 이해하자.

#include <iostream>
#include <string>
#include <queue>

using namespace std;

int main()
{
	int testcase;
	int M, N;
	int num; //받은 문서
	scanf("%d", &testcase); //testcase 입력

	while (testcase--) {
		priority_queue<int> pq; queue<pair<int, int>> q; //우선순위 큐와 큐 선언
		scanf("%d %d", &N, &M); //N은 문서의 수, M은 몇번째로 인쇄되었는지 궁금한 문서의 위치
		for (int i = 0; i < N; i++) { //N개 만큼 문서받기
			scanf("%d", &num);
			pq.push(num); //우선순위 큐에 삽입
			q.push(make_pair(i, num)); //큐안에 들어간 문서의 자리와 문서 삽입.
		}
		int count = 1; //매번 count는 1로 초기화
		while (1) {
			int key = pq.top(); //우선순위 큐의 맨 앞에 있는것(가장 큰 수)를 변수에 저장;

			if (key == q.front().second) { //큐의 맨앞에 있는수가 가장 큰 수 일때
				if (q.front().first == M) { //문서의 위치가 M과 일치한다면
					printf("%d\n", count); //count 출력 후 break
					break;
				}
				else { //큐의 맨앞에 있는수가 가장 큰 수이지만 원하는 위치에 있던 수가 아닐 떄
					q.pop(); pq.pop(); count++; //큐와 우선순위 큐에서 맨앞의 값을 제거해주고 count값 증가.
				}
			}
			else { //큐의 맨앞에 있는 수가 가장 큰 수가 아닐 때.
				q.push(q.front()); //맨 앞에 있는 값을 큐의 맨 뒤에 삽입.
				q.pop(); //맨 앞에 있는 값 제거
			}
		}
	}
}