백준/1927번/최소 힙/실버2

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

문제 설명

Site: Baekjoon
Number: 1927
Category: Heap
Rank: Silver 2

주어진 입력에 따라 0이 아닌 경우 최소 힙에 원소를 삽입하고, 0인 경우 힙이 비었을 때 0을 출력, 비어있지 않을 때 최소 값을 출력하는 문제이다.

queue헤더에 있는 priority_queue를 사용하고, 기존에 내림차순으로 되어있는 priority_queue를 오름차순으로 바꾼다면 쉽게 풀이가 가능하다.

#include <iostream>
#include <queue>

using namespace std;

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	unsigned int num;

	int N;
	cin >> N;

  //기존에 less<>로 최대 힙이 되어있기 때문에 greater<>을 통해 최소 힙으로 바꿔주어야한다
	priority_queue<unsigned int, vector<unsigned int>, greater<>> pq;

	for(int i = 0; i < N; i++)
	{
		cin >> num;

		if (num == 0)
		{
			if (pq.empty())
				cout << 0 << "\n";
			else
			{
				cout << pq.top() << "\n";
				pq.pop();
			}
		}
		else
			pq.push(num);
	}

	return 0;
}