BOJ 11286 : 절댓값 힙 (priority_queue, compare)

삼성 B형 전체 링크

 

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

 

 

절댓값 힙 문제를 STL을 적용해서 풀어보자.

위 링크에서 절댓값에 대한 우선순위를 아래와 같이 정의하였다.

int isMin(int a, int b)
{
	if (abs(a) < abs(b)) return 1; /* 절댓값 중 작으면 우선순위가 크다 */
	if (abs(a) == abs(b) && a < b) return 1; /* 같은 절댓값이면 음수가 우선순위가 크다 */

	return 0;
}

 

따라서 STL의 priority queue에서 compare는 아래와 같이 변경된다. 비교 연산의 방향에 유의하자.

 

절댓값 중 작으면 우선순위가 크다는 것은

parent가 크면 교환한다는 의미이므로 parent > child 일 때 true가 된다.

struct compare
{
	bool operator()(const int& parent, const int& child) const
	{
		/* 절댓값 중 작으면 우선순위가 크다 -> parent가 크면 교환한다. */
		if (abs(parent) > abs(child)) return true; 
		if (abs(parent) == abs(child) && parent > child) return true; 

		return false;
	}
};

 

그리고 pq의 type이 아래와 같이 변경된다. 따라서 clear도 변경된다.

priority_queue<int, vector<int>, compare> pq;

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

 

최종 코드는 아래와 같다.

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

using namespace std;

int N;

int abs(int x)
{
	return (x > 0) ? x : -x;
}

struct compare
{
	bool operator()(const int& parent, const int& child) const
	{
		/* 절댓값 중 작으면 우선순위가 크다 -> parent가 크면 교환한다. */
		if (abs(parent) > abs(child)) return true; 
		if (abs(parent) == abs(child) && parent > child) return true; 

		return false;
	}
};

priority_queue<int, vector<int>, compare> pq;

void pq_clear(priority_queue<int, vector<int>, compare>& pq)
{
	priority_queue<int, vector<int>, compare> 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;
}