백준 1927번 C++

백준 1927번 최소 힙

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

1927번: 최소 힙

정답 코드

#include <stdio.h>
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int N, x;
	cin >> N;
	priority_queue<int, vector<int>, greater<int>> pQ;
	for (int i = 0; i < N; i++) {
		cin >> x;
		if (!x) {
			if (pQ.empty()) cout << "0\n";
			else {
				cout << pQ.top() << "\n";
				pQ.pop();
			}
		}
		else
			pQ.push(x);
	}
	return 0;
}

문제 풀이

최소 힙을 구현하는 문제입니다. 최소 힙은 힙 구조를 이용해서 구현할 수 있습니다. 저는 우선순위 큐를 이용해서 문제를 풀었습니다. 우선순위 큐는 큐에 삽입을 하면 자동적으로 정렬을 해주는 자료구조입니다.