백준 / 1927 최소 힙 C++

www.acmicpc.net/problem/1927

1927번: 최소 힙

간단한 문제 하나만 풀고 집에 가려했는데 너무 간단한 문제였습니다. 

(사실 시간초과 한 번 나서 cin, cout 시간 줄이는 코드 사용)

 

그냥 우선순위 큐를 사용해 출력시키면 됩니다. 

우선순위 큐는 큐에 값을 push할 때마다 오름차순, 혹은 내림차순으로 정렬합니다. (따로 기준 만들어서 하는 것도 가능)

 

기본형은 int를 기준으로 priority_queue<int>pq = priority_queue<int, vector<int>, less<int>>pq 입니다.

기본형은 오름차순으로 정렬이 되며 (top위치에 가장 큰 값) priority_queue<int, vector<int>, greater<int>>pq 일 때 내림차순으로 정렬이 됩니다. (top 위치에 가장 작은 값) 

 

우선순위 큐는 O(nlogn) 으로 정렬을 하기 때문에 정렬의 특징과 큐의 특징이 동시에 필요하다면 반드시 써야하는 자료구조입니다. (중요!)

 

또한 컴파일러마다 greater<int>>pq 부분을 비트연산으로 처리하는 경우가 있어 띄어쓰기에 유의해야합니다.

 

코드는 다음과 같습니다.

#include<iostream>
#include<queue>
#include<vector>

using namespace std;

int n;
priority_queue<int, vector<int>, greater<int> >pq;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n;
	while (n--) {
		int num;
		cin >> num;
		if (num == 0) {
			if (pq.empty())
				cout << 0 << '\n';
			else {
				cout << pq.top() << '\n';
				pq.pop();
			}
		}
		else {
			pq.push(num);
		}
	}
}