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

 

알고리즘 분류: 자료구조, 우선순위 큐

문제 링크: https://www.acmicpc.net/problem/1927

1927번: 최소 힙

 

 

【 풀이 】

 

C++ STL의 priority_queue(우선순위 큐)를 이용하면 쉽게 해결할 수 있다.

 

우선순위 큐는 큐의 한 종류로, 우선순위에 따라 정렬된 큐이다.

특정 원소가 삽입(push)되면 주어진 우선순위에 따라 큐가 정렬되고,

삭제(pop)은 정렬된 큐의 맨 앞에서 이루어진다. 

특정 원소를 삽입해서 생기는 정렬 과정은 O(logN)의 시간 복잡도를 가지기에 시간 제한에 걸리지 않고 해결할 수 있다.

 

 

 

 

【 코드 】

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

int heap[100001];
priority_queue<int,vector<int>,greater<int>>pq;		//	내림차순으로 정렬해주는 큐 선언
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
    
	int n;
	cin >> n;
    
	for (int N = 0; N < n; 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);
		}
	}
	return 0;
}