[C++] 큐(Queue), 우선순위 큐(Priority Queue)

큐(Queue)

큐

 

문제

 

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

1966번: 프린터 큐

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

int main()
{
	int t;
	cin >> t;
	while (t--) {
		int n, m;
		cin >> n >> m;

		queue<pair<int, bool>> q;
		vector<int> v(n);
		for (int i = 0; i < n; i++) {
			cin >> v[i];
			if (i == m)
				q.push(make_pair(v[i], true));
			else
				q.push(make_pair(v[i], false));
		}

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

		int result = 0;
		while (!q.empty()) {
			if (q.front().first == v.back()) {
				result++;
				v.pop_back();

				if (q.front().second) {
					cout << result << '\n';
					break;
				}
			}
			else 
				q.push(q.front());

			q.pop();
		}
	}
}

 

우선순위 큐(Priority Queue)

top, pop에서 추출되는 원소는 제일 먼저 들어온 값이 아닌 현재 우선순위 큐 안에서 제일 우선순위가 높은 원소이다.

보통 힙(Heap) 자료구조로 구현된다.

 

문제

 

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

11279번: 최대 힙

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

int main(void)
{
	int n;
	cin >> n;

	// less<int>가 생략된 상태
	// 큰 것부터 뽑는다.
	priority_queue<int> q;
	while (n--) {
		int x;
		cin >> x;

		if (x == 0) {
			if (q.empty())
				cout << "0\n";
			else {
				cout << q.top() << "\n";
				q.pop();
			}
		}
		else
			q.push(x);
	}
}

 

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

1927번: 최소 힙

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

int main(void)
{
	int n;
	cin >> n;

	// 작은 것부터 뽑는다.
	priority_queue<int, vector<int>, greater<int>> q;
	while (n--) {
		int x;
		cin >> x;

		if (x == 0) {
			if (q.empty())
				cout << "0\n";
			else {
				cout << q.top() << "\n";
				q.pop();
			}
		}
		else
			q.push(x);
	}
}

 

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

11286번: 절댓값 힙

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

struct compare {
	bool operator()(int a, int b) {
		if (abs(a) == abs(b))
			return a > b;
		return abs(a) > abs(b);
	}
};

int main(void)
{
	int n;
	cin >> n;

	priority_queue<int, vector<int>, compare> q;
	while (n--) {
		int x;
		cin >> x;

		if (x == 0) {
			if (q.empty())
				cout << "0\n";
			else {
				cout << q.top() << "\n";
				q.pop();
			}
		}
		else
			q.push(x);
	}
}

 

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

1715번: 카드 정렬하기

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

int num[10001];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	cin >> N;
	priority_queue<int, vector<int>, greater<int>> pq;
	for (int i = 0, tmp; i < N; ++i) {
		cin >> tmp;
		pq.push(tmp);
	}

	int ans = 0;
	while (!pq.empty()) {
		int tmp = pq.top();
		pq.pop();

		if (!pq.empty()) {
			tmp += pq.top();
			pq.pop();

			ans += tmp;
			pq.push(tmp);
		}
	}
	cout << ans;
}

 

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

1655번: 가운데를 말해요

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

int main()
{
	int n, m;
	cin >> n;

	priority_queue<int> low; // 중간값과 작은 수
	priority_queue<int, vector<int>, greater<int>> high; // 큰 수
	while (n--) {
		cin >> m;

		// 규칙1. low.size() >= high.size()
		if (low.size() > high.size())
			high.push(m);
		else
			low.push(m);

		// 규칙2. low.top() <= high.top()
		if (!high.empty() && !low.empty() && low.top() > high.top()) {
			int a = high.top(), b = low.top();
			high.pop(), low.pop();
			high.push(b), low.push(a);
		}
		cout << low.top() << '\n';
	}
}