[백준 14235] 크리스마스 선물

문제 풀이

 

산타 할아버지는 아이들에게 선물을 줄 때, 가장 가치가 큰 선물을 준다.

선물 보따리에 머가 들었는지 모르겠지만 꺼냈을 때 그 가치가 가장 큰 것을 뽑으려면 최대 힙 구조로 구현하면 된다.

따라서 우선순위 큐를 최대 힙으로 구성해서 뽑으면 된다.

 

소스 코드

 

#include <iostream>
#include <queue>

using namespace std;

int n, a, x;
priority_queue<int> pq;
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	while (n--)
	{
		cin >> a;
		if (a == 0)
		{
			if (pq.empty())
				cout << "-1\n";
			else
			{
				cout << pq.top() << '\n';
				pq.pop();
			}
		}
		else
		{
			for (int i = 0; i < a; i++)
			{
				cin >> x;
				pq.push(x);
			}
		}
	}

	return 0;
}