[c++] 백준 11279, 1927 최대 힙, 최소 힙

백준 단계별로 풀어보기 [우선순위 큐] 최대 힙, 최소 힙

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

11279번: 최대 힙

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

1927번: 최소 힙

 

[풀이]

우선순위 큐는 priority_queue<자료형, 구현체, 비교 연산자>의 형식으로 선언하여 사용할 수 있다. 기본 max_heap으로 구현이 되어있고 min_heap을 이용하려면 비교 연산자 자리에 greater<>를 넣어 선언한다. 

cin, cout 을 사용하면서 시간초과가 발생할 수 있으므로

std::ios::sync_with_stdio(false);
std::cin.tie(NULL);
std::cout.tie(NULL);

를 앞에 넣어준다.

 

[코드]

#include <iostream>
#include <algorithm>
#include <queue>

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);
	std::priority_queue<int> pq;
	int n;
	std::cin >> n;
	int a;
	for (int i = 0; i < n; i++) {
		std::cin >> a;
		if(a != 0)	
			pq.push(a);
		else {
			if (!pq.empty()) {
				std::cout << pq.top() << "\n";
				pq.pop();
			}
			else std::cout << "0\n";
		}
	}
}