BOJ 11279 : 최대 힙 (priority_queue)

삼성 B형 전체 링크

 

https://www.acmicpc.net/problem/11279

 

 

우선순위 큐의 문제인 최대 힙을 STL - queue(priority_queue)로 풀어보자.

 

먼저 priority_queue의 메서드는 아래의 4개가 있다.

 

push()	pq에 원소를 넣는다.
pop()	pq에 원소를 뺀다.
top()	pq에서 가장 우선순위가 높은 값을 return 한다. (pure한 코드에서 heap[1]과 동일)
size()	pq의 크기를 return 한다.
empty()	pq가 비어있으면 true, 아니면 false를 return 한다.
clear()	clear가 없다.

 

pure한 코드와 다른 점은, pq.pop()이 값을 리턴하지는 않는다. 원소를 빼기만 한다.

pop이 void로 만들어져있는 것을 알 수 있다.

 

두 번째로 다른 점은 clear가 없는 것이다.

따라서 empty가 true가 될 때까지 pop하는 방법이 있다.

while (!pq.empty()) pq.pop();

 

그러나 B형처럼 tc가 큰 경우에 위의 방법을 쓰면, 남아있는 queue의 size 만큼 비용이 든다.

따라서 clear를 구현할 필요가 있다.

 

clear할 pq를 reference로 넘겨준 후, pq_clear 함수에서 reset을 선언하고 swap으로 교체하면 된다.

void pq_clear(priority_queue<int>& pq)
{
	priority_queue<int> reset;
	swap(pq, reset);
}

swap된 pq는 초기화된 reset이 되고, reset은 pq_clear에서 stack 영역에 선언되었으므로 메모리가 해제된다.

 

아래의 코드로 직접 확인해보자.

#include <stdio.h>
#include <iostream>
#include <queue>

using namespace std;

priority_queue<int> pq; 

void pq_clear(priority_queue<int>& pq)
{
	priority_queue<int> reset;
	swap(pq, reset);
}

int main(void)
{
	for(int i = 0; i < 10; i++) pq.push(i);

	for (int i = 0; i < 5; i++)
	{
		printf("%d\n", pq.top());
		pq.pop();
	}
    
	//while (!pq.empty()) pq.pop();
	pq_clear(pq);
	
	printf("%d\n", pq.size());

	return 0;
}

---

이제 최대 힙 문제를 풀어보자.

 

priority_queue를 선언하면 default가 최대 힙이다.

따라서 아래의 코드로 문제를 풀 수 있다.

#include <stdio.h>
#include <iostream>
#include <queue>

using namespace std;

int N;
priority_queue<int> pq; 

void pq_clear(priority_queue<int>& pq)
{
	priority_queue<int> reset;
	swap(pq, reset);
}

int main(void)
{
	scanf("%d", &N);

	pq_clear(pq);

	for (int i = 0; i < N; i++)
	{
		int x;

		scanf("%d", &x);
		if (x) pq.push(x);
		else
		{
			if (!pq.empty())
			{
				printf("%d\n", pq.top());
				pq.pop();
			}
			else
				printf("0\n");
		}
	}

	return 0;
}