[C++][BOJ 백준]11286_절댓값 힙

문제 번호

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

11286번: 절댓값 힙

 

 

알고리즘 분류

자료 구조
우선순위 큐

 

문제 풀이

 우선순위 큐를 다루어야하는 문제이다. <queue> 헤더에 있는 priority_queue 를 사용하기로 하였다.

priority_queue<자료형, 구현체, 비교 연산자> 로 정의된다. 

 

- 자료형은 int, double 등등 우리가 알고있는 자료형들을 넣으면 된다.

- 구현체는 기본적으로 vector<자료형>으로 정의된다. 

- 비교 연산자는 less<자료형>이 기본이다. 오름차순으로 사용하고 싶다면 greater<자료형> 을 사용하도록하자.

 

priority_queue의 사용법을 몰랐을때는 어렵게 느껴졌지만 사용법을 알면 문제에서 요구하는대로 구현하기만 하면 되는 문제이다.

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

struct comp
{
	bool operator()(int a, int b)
	{
		if (abs(a) == abs(b))
			return a > b;
		else
			return abs(a) > abs(b);
	}
};

void Solution(int n)
{
	priority_queue< int, vector<int>, comp > pq;

	while (n--)
	{
		int Command; cin >> Command;

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

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

	int n; cin >> n;
	Solution(n);

	return 0;
}

특이사항

-無-