[백준] 11286번. 절댓값 힙

[백준] 11286번. 절댓값 힙

1. 문제

절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다.

1. 배열에 정수 x (x ≠ 0)를 넣는다.
2. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이

가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.
프로그램은 처음에 비어있는 배열에서 시작하게 된다.

2. 입력

첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 절댓값이 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 정수는 -231보다 크고, 231보다 작다.

3. 출력

입력에서 0이 주어진 회수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 절댓값이 가장 작은 값을 출력하라고 한 경우에는 0을 출력하면 된다.

4. 풀이

• 음수 우선 순위 큐와 양수 우선 순위 큐를 각각 생성하고 각 우선 순위 큐의 top을 비교해가며 결과를 출력한다.
• 처음에는 음수인지 양수인지 저장하는 boolean를 사용할까 하다가 그냥 우선 순위 큐` 두 개 만들어서 풀었다.

5. 처음 코드와 달라진 점

• 처음에 command==0인 경우를 첫 if로 처리했는데 첫 if만 너무 길고 else-if와 else가 짧아서 가독성이 떨어지는 것 같아서 순서를 바꾸었다.
• c++ 우선 순위 큐는 기본으로 내림차순이라 음수는 그대로 넣어주고 양수는 음수로 전환해서 넣어줬는데 둘 다 바꾼 줄 알고 자꾸 -를 두 번 붙여서 1차 오류가 났다.
• 둘 다 음수로 처리 되어있어서 절대값 비교하려면 작다가 아니라 크다로 비교해야 하는데 반대로 했다.(처음에 음수에 -를 붙이는 방식으로 처리했을때 조건식을 수정 안 해서 생긴 일이었다.)

6. 코드

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


int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	
	priority_queue<int> positive_queue;
	priority_queue<int> negative_queue;

	int n;
	cin >> n;
	for (int i = 0; i < n; i++){
		int command;
		cin >> command;

		if (command > 0) positive_queue.push(-command);
		else if (command < 0) negative_queue.push(command);
		else{
			if (positive_queue.empty() && negative_queue.empty()) cout << 0<<"\n";
			else if (positive_queue.empty()) {
				cout << negative_queue.top()<<"\n";
				negative_queue.pop();
			}
			else if (negative_queue.empty()) {
				cout << -positive_queue.top() << "\n";
				positive_queue.pop();
			}
			else {
				int positive = positive_queue.top();
				int negative = negative_queue.top();
				if (positive > negative) {
					cout << -positive << "\n";
					positive_queue.pop();
				}
				else {
					cout << negative << "\n";
					negative_queue.pop();
				}
			}
		}
	}
}