[백준 1927번 C/C++] 최소 힙

[백준 1927번 C/C++] 최소 힙

 

 

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

1927번: 최소 힙

---

 

 

해결방안

 

풀이 방법은 여러가지다. 이번의 경우, priority_queue를 사용하였다.

 

priority_queue의 기본은 내림차순이다. 즉, 큰 수가 가장 위(앞쪽)에 있다.

---

 

priority_queue 정렬 방법

 

오름차순

priority_queue<int, vector<int>, greater<int> > pQ1;

 

 

내림차순

priority_queue<int, vector<int>, less<int>> pQ2;

• priority_queue의 기본형이 내림차순이므로 굳이 할 필요없다. 

 

※ #include <queue> 외의 헤더는 필요없다. 

 

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

int main() {
	priority_queue<int, vector<int>, greater<int> > pQ1;//오름차순
	priority_queue<int, vector<int>, less<int>> pQ2;//내림차순

	pQ1.push(2);
	pQ1.push(5);
	pQ1.push(2);
	pQ1.push(9);
	pQ1.push(7);
	pQ1.push(6);

	pQ2.push(2);
	pQ2.push(5);
	pQ2.push(2);
	pQ2.push(9);
	pQ2.push(7);
	pQ2.push(6);

	while(!pQ1.empty())
	{
		cout << pQ1.top() << " ";
		pQ1.pop();
	}

	cout << "\n";
	while(!pQ2.empty())
	{
		cout << pQ2.top() << " ";
		pQ2.pop();
	}

	return 0;
}

 

 

---

 

 

 

코드

 

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

int n;
long long x;
priority_queue<long long, vector<long long>, greater<long long>> pQ;

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

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> x;

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


	return 0;
}

 

 

---