🖊️ 문제

https://www.acmicpc.net/problem/1966

---

🖊️ 풀이

각 문서들의 우선순위와, 내가 찾아야하는 문서인지 여부를 pair로 만들어서 queue에 넣는다.

가장 큰 숫자들을 따로 vector에 넣어서 한 번 정렬한 뒤, pop_back()을 통해 꺼내 썼다.

---

벡터 이용

벡터 시간복잡도

삽입 : O(1)
정렬 : O(NlogN)
삭제(pop_back()) : O(1)
접근 : O(1)

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

int main()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	int TestCase, N, M;
	int priority;
	cin >> TestCase;

	for (int i = 0; i < TestCase ; i++) {
		// 각 테스트 케이스
		cin >> N >> M;

		queue<pair<int, bool>> q;
		vector<int> v;
		
		for (int j = 0; j < N; j++) {
			cin >> priority;
			if (j == M) q.push(make_pair(priority, true));
			else q.push(make_pair(priority, false));
			v.emplace_back(priority);
		}

		sort(v.begin(), v.end());

		int answer = 0;
		while (!q.empty()) {
			int max = v.back();
			while (q.front().first < max) {
				pair<int, bool> val = q.front();
				q.pop();
				q.push(val);
			}
			if (q.front().second) {
				answer++;
				break;
			}
			else {
				q.pop();
				v.pop_back();
				answer++;
			}
		}
		cout << answer << '\n';
	}
}

---

우선순위 큐 이용

이러한 역할을 priority_queue를 통해서 해도 된다.

우선순위 큐 시간복잡도

push : O(logN)
pop : O(logN)

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

int main()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	int TestCase, N, M;
	int priority;
	cin >> TestCase;

	for (int i = 0; i < TestCase ; i++) {
		// 각 테스트 케이스
		cin >> N >> M;

		queue<pair<int, bool>> q;
		priority_queue<int> pq;
		
		for (int j = 0; j < N; j++) {
			cin >> priority;
			if (j == M) q.push(make_pair(priority, true));
			else q.push(make_pair(priority, false));
			pq.push(priority);
		}

		int answer = 0;
		while (!q.empty()) {
			while (q.front().first < pq.top()) {
				pair<int, bool> val = q.front();
				q.pop();
				q.push(val);
			}
			if (q.front().second) {
				answer++;
				break;
			}
			else {
				q.pop();
				pq.pop();
				answer++;
			}
		}
		cout << answer << '\n';
	}
}