우선순위 큐

문제 

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

2075번: N번째 큰 수

 

솔루션

---

N^2의 격자판에서 N번째로 큰 수를 뽑아야 한다.

 

처음에 모든 수를 다 담은 뒤, 5번 째 큰 수를 뽑으려 했는데, 메모리 제한이 12MB인 것을 모르고 제출을 했다가.. 메모리 초과를 받았다.

 

 

따라서 우선순위 큐를 이용해 이를 해결하였는데, 원리는 다음과 같다.

 

입력으로 들어온 수 중에서 가장 큰 수 N개만 남겨놓고 모든 값들은 우선순위 큐에서 제거한다.

 

그러면 N번째 큰 수가 자동으로 pq.top()에 위치하게 되므로, 출력을 하면 된다.

 

 

코드

---

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

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; i < N; i++) {
		for (int j = 0; j < N; j++) {
			int value;
			cin >> value;

			pq.push(value);
			if (pq.size() > N) pq.pop();
		}
	}

	cout << pq.top();
}

 

---

문제

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

1715번: 카드 정렬하기

 

솔루션

---

카드를 합치는 데, 가장 작은 것 부터 합쳐가는 것이 비교 회수가 최소가 된다.

 

따라서 우선순위 큐를 이용하여 가장 작은 두 수를 뽑고, 더한 뒤 다시 우선 순위 큐에 넣어준다.

이때 큐에 넣는 값을 계속 정답에 더하면 된다.

 

 

코드

---

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

int N;
priority_queue<int> pq;

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

	cin >> N;
	for (int i = 0; i < N; i++) {
		int value;
		cin >> value;
		pq.push(-value);
	}

	long long ans = 0;

	while (pq.size() > 1) {
		int f = -pq.top();
		pq.pop();
		int s = -pq.top();
		pq.pop();

		ans += (f + s);
		pq.push(-(f + s));
	}
	cout << ans << '\n';
}