📖 Problem

🔓 Solve

이 문제에서 가장 핵심이 되고 중요한 부분은 현재 큐에서 가장 앞에 있는 문서의 중요도를 확인하는 작업이다.

여기서 중요도를 판단하기 위해 우선순위 큐 를 사용할 수 있다.

먼저 일반 큐와 우선순위 큐를 한 개씩 선언한다.

일반 큐에는 문서들의 순서가 담겨있고, 우선순위 큐는 각 문서의 중요도에 따라 정렬이 된다.

입력을 받은 대로 일반 큐와 우선순위 큐 모두에 문서를 삽입한다.

이후 찾으려는 문서가 나올 때까지 각 케이스별로 일반 큐의 상위값과 우선순위 큐의 상위값을 비교한다.

1. 값이 같으면 두 큐에서 모두 pop 연산을 한다. 이 때 찾으려는 문서이면 출력 후 종료한다.
2. 값이 다르면 다시 큐에 push 연산을 한다.

💻 Code

#include <iostream>
#include <queue>

using namespace std;

struct data_pos {
	int pos;
	int importance;
};

int main() {
	int T;
	// test num
	cin >> T;

	int N, M;

	for (int count = 0; count < T; count++) {
		cin >> N >> M;
		priority_queue<int> p_que;
		queue<data_pos> que;

		int imp;
		int index = 1;
		for (int inner_count = 0; inner_count < N; inner_count++) {
			cin >> imp;
			p_que.push(imp);
			que.push(data_pos{inner_count, imp});
		}

		while (!que.empty()) {
			data_pos data = que.front();
			que.pop();

			if (data.importance == p_que.top()) {
				p_que.pop();

				if (data.pos == M) {
					cout << index << endl;
					break;
				}

				index++;
			}
			else {
				que.push(data);
			}

		}


	}
}

우선순위 큐의 개념을 알고 있는지 확인하는 문제라고 생각한다.

⚡개인적으로 공부하면서 포스팅한 글입니다. 오류가 있는 경우 지적해주시면 감사하겠습니다!⚡