[C++] 백준 11279: 최대 힙

문제

[C++] 백준 11279: 최대 힙 SILVER 2
https://www.acmicpc.net/problem/11279

 

---

 

접근 방법

이 문제는 최대 힙(Max Heap)을 직접 구현하는 대신,
C++의 priority_queue를 이용해 처리하는 전형적인 자료구조 문제다.

 

문제의 규칙은 간단하다.

• 입력값 x가 0이 아니면 → 자료구조에 값을 넣고
• 입력값 x가 0이면
  • 비어 있으면 0 출력
  • 비어 있지 않으면 가장 큰 값을 출력하고 제거

C++의 priority_queue<int>는 기본적으로 가장 큰 값이 top에 오는 최대 힙 구조이기 때문에 문제 조건과 정확히 일치한다.

따라서 별도의 힙 구현 없이 입력에 따라 push, top, pop만 사용하면 된다.

 

구현 시 주의할 점

• priority_queue<int>는 기본이 내림차순(최대 힙) 이라는 점을 알고 있어야 한다.
• 모든 연산은 아래와 같으므로 전체 시간 복잡도는 충분히 제한 내에서 동작한다.
  • 삽입 O(log N)
  • 삭제 O(log N)

 

---

 

코드

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

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

	int n = 0;
	cin >> n;

	priority_queue<int> pq;
	for (int i = 0; i < n; i++)
	{
		int x = 0;
		cin >> x;

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

	return 0;
}