[C/C++] 백준 11279번 - 최대 힙 (우선순위 큐)

 

 

<코드>

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

int N, x;
priority_queue<int> pq;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> x;
		if (x == 0)
		{
			if (pq.empty()) printf("0\n");
			else
			{
				printf("%d\n", pq.top());
				pq.pop();
			}
		}
		else pq.push(x);
	}

}

 

풀이 방법

ios_base::sync_with_stdio(0);
cin.tie(0);

시간 초과가 발생하지 않게 위 코드 삽입해주시고 endl 대신 '\n'를 사용해주도록 합니다.

이 문제의 경우 우선순위 큐를 직접 구현해도 되지만 STL라이브러리에서 제공하는 priority_queue를 사용하여 쉽게 풀이가 가능합니다.

우선순위 큐와 일반 큐의 차이점은 일반 큐의 경우 대포에 포탄을 넣듯이 순차적으로 들어가서 순차적으로 나오지만
우선순위 큐는 삽입할 때 자동적으로 내림차순 정렬되어 삽입됩니다. 따라서 우선순위 큐에 원소를 삽입 후 pop을 해주면 큰 순서대로 출력이 가능합니다.

 

www.acmicpc.net/problem/11279

11279번: 최대 힙