백준 11279 c++ "최대 힙" -[PlusUltraCode]

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

11279번: 최대 힙

 

[필자 사고]

 

최대 힙을 구하라는 문제이다.

 

최대 힙과 가장 연관있는 알고리즘은 우선순위 큐이다. 

 

개발자가 원하는대로 정렬 시스템을 설계하면 이 문제를 쉽게 해결할 수 있따.

 

c++내의 우선순위큐를 선언만 하면 자동으로 큰 값이 우선되게 정렬 되어 있다.

 

이제 알고리즘을 정했다면 시간복잡도에 어긋나지 않는지 판단해야 된다.

 

N=10000 가 주어진다.

 

우선순위큐의 시간복잡도는 Nlog(N) 이므로 1초 안에 문제를 해결할 수 있다.

 

[소스 코드]

 

 

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

priority_queue<long, vector<long>> pq;

int N;

void Input() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		long num;
		cin >> num;
		if (num == 0) {
			if (pq.empty()) {
				cout << 0 << '\n';
				continue;
			}
			cout << pq.top() << '\n';
			pq.pop();
		}
		pq.push(num);
	}
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	Input();
}