(백준/C++) 11286_절댓값 힙

11286번: 절댓값 힙 (acmicpc.net) 문제는 힙을 절대값을 고려해서 만드는 문제입니다.

힙(heap)이란, 최대값이나 최소값을 빠르게 찾기 위한 완전 이진 트리를 기본으로 한 자료구조로, 매 삽입/삭제시 조건을 만족하는 정렬을 수행합니다.

이때 부모(P)와 자식(C) 사이의 정렬을 수행하지만, 자식간(LC, RC)의 정렬은 보장하지 않아도 되기 때문에 $O(logN)$의 수행 시간을 갖습니다.

(최소/최대 값을 찾는 시간 복잡도는 $O(1)$이지만, pop을 수행한다면 $O(logN)$이 됩니다.)

접근 방법

이 문제는 절대 값을 포함한 최소 힙(Min Heap) 문제로 볼 수 있습니다.

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

따라서 이 문제는

1. 최소 힙(Min Heap) 자료구조를 사용하고
2. 절댓값을 기준으로 최소 힙을 구성하되, 절댓값이 같을 경우 실제 값이 작은 것을 우선으로 정렬하면 됩니다.

부모 요소 인덱스 찾기

• index 0 부터 시작하는 경우, 부모의 인덱스는 $(Child - 1) / 2$로 구할 수 있습니다.

자식 요소 인덱스 찾기

• index 0 부터 시작하는 경우, 왼쪽 자식은 $Parent * 2 + 1$로 구할 수 있습니다.
• 오른쪽 자식은 쉽게 $LChild+1$로 구할 수 있습니다.

---

풀이

이 문제를 풀 때, 고려해야 할 점은 절대 값이 같은 숫자의 경우입니다.

위에서부터 아래쪽으로 검사할 때(pop), 자식의 선택에 있어서도 이 조건이 고려되어야 합니다.

abs(heap[lchild]) == abs(heap[rchild]) && heap[lchild] < heap[rchild]

LChild와 RChild의 절대 값이 같은 경우, 가장 작은 수를 선택합니다.

#include <iostream>
using namespace std;

class absoluteHeap
{
public:
	absoluteHeap(int n)
	{
		heap = static_cast<int*>(malloc(sizeof(int) * n));
		reserveSize = n;
	}
	~absoluteHeap()
	{
		free(heap);
	}

	void input(int num)
	{
		// 0이 입력되면 출력 후 pop한다.
		if(num == 0)
			cout << pop() << '\n';
		else
			push(num);
	}

private:
	// 1.절대값이 작은 숫자를 위로 보내고
	// 2.같은 수인 경우 작은 숫자를 위로 보낸다
	void push(int n)
	{
		if (currentSize >= reserveSize) return;

		heap[currentSize++] = n;

		int child = currentSize - 1;
		int parent = (child - 1) / 2;

		while (child > 0 && abs(heap[parent]) >= abs(heap[child]))
		{
			// 2-1.부모가 자식보다 작으면, 정렬이 완료된 것으로 보고 종료한다
			if (abs(heap[parent]) == abs(heap[child]) && heap[parent] < heap[child]) break;

			swap(heap[parent], heap[child]);

			child = parent;
			parent = (child - 1) / 2;
		}
	}

	int pop()
	{
		if (currentSize <= 0) return 0;

		int result = heap[0];

		heap[0] = heap[--currentSize];

		int parent = 0;

		while (parent < currentSize)
		{
			int lchild = parent * 2 + 1;
			int rchild = lchild + 1;
			int child = -1;

			if(lchild < currentSize && rchild < currentSize)
			{
				if (abs(heap[lchild]) < abs(heap[rchild]) || // 절대값이 작거나
					(abs(heap[lchild]) == abs(heap[rchild]) && heap[lchild] < heap[rchild])) // 같은 경우 음수 쪽을 선택한다.
					child = lchild;
				else
					child = rchild;
			}
			else if(lchild < currentSize)
			{
				child = lchild;
			}

			if(child != -1 && abs(heap[parent]) > abs(heap[child]) || // 절대값이 작거나
				(abs(heap[parent]) == abs(heap[child]) && heap[parent] > heap[child])) // 같은 경우 음수 라면 바꾼다.
			{
				swap(heap[parent], heap[child]);
				parent = child;
			}
			else
			{
				break; // child가 없는 경우 종료한다
			}
		}

		return result;
	}

private:
	int* heap;
	int reserveSize = 0;
	int currentSize = 0;
};

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

	int N;
	cin >> N;

	absoluteHeap heap = absoluteHeap(N);

	while(N--)
	{
		int tmp;
		cin >> tmp;
		heap.input(tmp);
	}
}