[백준 #1927] 최소 힙 (C++)

 

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

1927번: 최소 힙

 

입력하는 정수가 자연수라면 배열에 그 정수를 추가하고,

0이라면 배열에서 가장 작은 값을 출력하고 그 값을 제거하는 문제이다.

 

작은 데이터일수록 우선순위가 높은 우선순위 큐를 만들기 위해

priority_queue <int, vector <int>, greater <int>> q; 로 큐를 생성했다.

 

큐는 앞에서 원소를 빼기 때문에 가장 작은 원소를 출력 후 삭제하려면

오름차순 정렬을 해야되므로 오름차순으로 정렬해주는 greater를 추가했다.

 

처음엔 벡터로 코드를 작성했는데 erase와 min_element 때문인지 시간 초과가 떴다.

그래서 벡터가 아닌 우선 순위 큐를 사용하여 코드를 작성했더니 

코드도 훨씬 간결해지고 시간을 줄이는 데에 성공했다.

 

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

priority_queue <int, vector <int>, greater <int>> q;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int n, num;
	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> num;
		if (num != 0) {
			q.push(num);
		}
		else {
			if (q.empty()) {
				cout << 0 << "\n";
			}
			else {
				cout << q.top() << "\n";
				q.pop();
			}
		}
	}
	return 0;
}