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

 

1) 문제설명

백준 Online Judge 1927번 최소힙

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

1927번: 최소 힙

 

2) 해결방법

O(n)의 시간을 맞춰야 하므로 우선순위 큐를 이용하여 구현한다.

 

3) 코드

#include<iostream>
#include<queue>
#include<deque>
#include<string.h>
#include<math.h>
#include<cmath>
#include<stack>
#include<algorithm>

using namespace std;

/*


*/
int main() {
	int n;
	priority_queue <int,vector<int>,greater<int>> pq;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int x;
		scanf("%d", &x);
		if (x != 0) {
			pq.push(x);
		}
		else {
			if (pq.empty()) {
				printf("0\n");
			}
			else {
				printf("%d\n", pq.top());
				pq.pop();
			}		
		}
	}
}

priority_queue<int ,vector<int>,greater<int>>를 써서 우선순위를 오름차순으로 한다.