[C++]백준 11286번: 절댓값 힙

문제

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

11286번: 절댓값 힙

 

문제이해

 

• 첫째 줄에 연산의 개수(N)를 입력합니다.
• N개의 줄에 대해 연산의 정보(x)를 입력합니다.
• 입력에서 0이 입력된 수만큼 답을 출력합니다.

절댓값을 기준으로 정렬된 힙을 만들기 위해서는 당연히 절댓값을 기준으로 정렬한 우선순위 큐(priority_queue)를 사용하여야 합니다. 주의해야 할 점이 있다면 절댓값이 같고 부호가 다른 수에 대해서는 음수가 우선순위가 더 높게 하여야 합니다. 또한 수의 범위가 int로는 전부다 포함하지 못하기 때문에 long long 타입을 사용하여야 합니다.

 

 

다음은 위의 설명대로 만든 코드입니다.

문제풀이

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

struct absAscending
{
	bool operator()(const long long& a, const long long& b) const {
		long long absA = abs(a);
		long long absB = abs(b);

		if (absA != absB) {
			return absA > absB;
		}
		else {
			return a > b;
		}
	}
};

priority_queue<long long, vector<long long>, absAscending> test;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int N;
	long long C;
	cin >> N;
	while(N--) {
		cin >> C;
		if (C != 0)
			test.push(C);
		else {
			if (test.size() == 0)
				cout << "0\n";
			else {
				cout << test.top() << "\n";
				test.pop();
			}
		}
	}
}

 

문제후기

정렬 기준만 잘 세워준다면 어렵지 않은 문제였습니다.