[백준] 11286번 - 절댓값 힙

www.acmicpc.net

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

문제

💡

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

배열에 정수 x (x ≠ 0)를 넣는다.

배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

시간 제한: 1초

메모리 제한: 256MB

입력

💡

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

출력

💡

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

예제 입력	예제 출력
18 1 -1 0 0 0 1 1 -1 -1 2 -2 0 0 0 0 0 0 0	-1 1 0 -1 -1 1 1 -2 2 0

풀이

절댓값 힙 자료구조를 지원하지 않는다라 가정하고, 절대값이 가장 작은 값을 삭제한다는 부분에서 최소힙을 떠올렸다.

먼저, 배열에 입력하기 전에 절댓값으로 변환하는 방법으로 구현해봤다. 그런데 절댓값이 가장 작은 값이 여러개 일때 그 중 가장 작은 값을 구해야하는 문제가 있다.

이 때, 같은 값이 여러개가 나온다고 함은 음수부호인 경우와 양수부호인 경우, 같은 값을 넣었을 경우 인데, 절댓값으로 변환하면 이런 구분이 어려워진다. 그래서 절댓값과 원본값을 같이 저장하는 방법을 모색해봤다.

std::priority_queue를 분석해 보니 마지막 매개변수가 템플릿 문법을 사용이 가능해 절대값을 비교할 수 있는 구조체를 만들었다.

구현해보면서 알았는데 비교연산자를 구현할 때 최소힙은 >을, 최대힙은 <을 구현해야 한다는 것이다.

제출 코드


#include <iostream>
#include <queue>
using namespace std;
struct Value {
	int value;
	Value(int v) : value(v) {}
	bool operator>(const Value& other) const {
		if (abs(value) == abs(other.value)) {
			return value > other.value;
		}
		else {
			return abs(value) > abs(other.value);
		}
	}
};

int main() {
	cin.tie(NULL);
	std::ios::sync_with_stdio(false);
	
	priority_queue<Value, vector<Value>, greater<Value>> minHeap; // 최소 힙
	int n;

	// 연산의 개수 입력
	do {
		cin >> n;
	} while (1 > n || n > 100000);

	// 연산에 대한 정보 입력
	for (int i = 0; i < n; ++i) {
		int x;
		do{
			cin >> x;
		} while (-231 > x || x > 231);

		if (x == 0) {
			if (minHeap.empty()) {
				cout << "0\n";
			}else {
				cout << minHeap.top().value << "\n";
				minHeap.pop();
			}
		}else {
			minHeap.push(Value(x));
		}
	}

	return 0;
}

시간 초과가 발생했다.

혹시나 해서 입력을 제한하기 위해 만든 while문을 지웠더니 정답이다.

입력될 값의 범위가 정해져있어 코드에서도 제한해야겠다 생각했는데 다시 생각해보니 제한하라는 말이 없어서 굳이 그럴 필요가 없을지도 모르겠다.

코드


#include <iostream>
#include <queue>
using namespace std;
struct Value {
	int value;
	Value(int v) : value(v) {}
	bool operator>(const Value& other) const {
		if (abs(value) == abs(other.value)) {
			return value > other.value;
		}
		else {
			return abs(value) > abs(other.value);
		}
	}
};

int main() {
	cin.tie(NULL);
	std::ios::sync_with_stdio(false);
	
	priority_queue<Value, vector<Value>, greater<Value>> minHeap; // 최소 힙
	int n;

	// 연산의 개수 입력
	cin >> n;

	// 연산에 대한 정보 입력
	for (int i = 0; i < n; ++i) {
		int x;
			cin >> x;

		if (x == 0) {
			if (minHeap.empty()) {
				cout << "0\n";
			}else {
				cout << minHeap.top().value << "\n";
				minHeap.pop();
			}
		}else {
			minHeap.push(Value(x));
		}
	}

	return 0;
}