[1927] C++ : 최소 힙

문제

널리 잘 알려진 자료구조 중 최소 힙이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.

1. 배열에 자연수 x를 넣는다.
2. 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다.

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

입력

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

출력

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

예제 입력 1 

9
0
12345678
1
2
0
0
0
0
32

예제 출력 1 

0
1
2
12345678
0

 

풀이

처음에 이 문제를 딱 마주쳤을 때는 heap이니까 complete binary tree이고 그냥 구조체로 만들어야겠다고 생각했다. 그래서 무식하게 코드를 만들었다. 

 

<잘못된 코드>

#include<iostream>
#include<queue>
#include<algorithm>

typedef struct binarytree{
	int data;
	struct binarytree* leftchild;
	struct binarytree* rightchild;
}Tree;

using namespace std;

Tree* r;

void minsort();
void insert( int data);

void insert( int data)
{
	queue<Tree*> q;
	Tree* curr = (Tree*)malloc(sizeof(Tree));
	curr->leftchild = NULL;
	curr->rightchild = NULL;
	curr->data = data;
	if (!r)
	{
		r = curr;
		return;
	}
	for (q.push(r); !q.empty();)
	{
		Tree* p = q.front();
		q.pop();
		if (p->data > curr->data)
			swap(p->data, curr->data);
		if (!p->leftchild)
		{
			p->leftchild = curr;
			break;
		}
		else if (!p->rightchild)
		{
			p->rightchild = curr;
			break;
		}
		q.push(p->leftchild);
		q.push(p->rightchild);
	}
	
	
	
}

void minsort()
{
	for (Tree * p = r; p;)
	{
		if (p->leftchild && p->data > p->leftchild->data && p->leftchild->data>=0) {
			swap(p->data, p->leftchild->data);
			p = p->leftchild;
		}
		else if (p->rightchild && p->data > p->rightchild->data && p->rightchild->data >= 0) {
			swap(p->data, p->rightchild->data);
			p = p->rightchild;
		}
		else
			break;
	}
}


void deleteroot()
{
	Tree* null = NULL;
	cout << r->data << "\n";

	queue<Tree*> q;
	for (q.push(r); ;)
	{
		if (q.empty()) {
			r->data = -1;
			break;
		}
		Tree* p = q.front();
		q.pop();
		if (!p->leftchild && p->data >=0)
		{
			r->data = p->data;
			p->data = -1;
			break;
		}
		else if (!p->rightchild && p->leftchild->data >=0)
		{
			r->data = p->leftchild->data;
			p->leftchild->data = -1;
			break;
		}
		else
		{
			if(p->rightchild->data >=0)
				q.push(p->rightchild);
			if (p->leftchild->data >= 0)
				q.push(p->leftchild);
		}

	}
	minsort();

}


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

	int num;
	cin >> num;
	for (int i = 0; i < num; i++)
	{
		int number;
		cin >> number;
		if (number == 0)
		{
			if (!r || r->data == -1)
				cout << 0 << "\n";
			else
				deleteroot();

		}
		else {
			insert(number);
		}

	}
	//inorder(r);
	return 0;
}

 

일단 예제는 돌아가는 멋진 코드였다. 근데 정말 읽기도 어렵고 무엇보다 심각한 것이 시간초과를 일으킨다는 것이었다. 이 코드를 이리저리 만져보았지만, 시간초과를 잡을 만한 요소가 보이지 않았고, 무엇보다도 코드가 너무 지저분해서 오답일 경우에 고치기 힘들다는 단점이 있었다. 

그러다가 좋은 생각이 났다. 힙을 구현하는 가장 간단한 방법은 배열이다. 이 기본적인 사실을 간과해 이 문제를 너무 어렵게 해결하고 있었다.

complete binary tree를 배열로 구현하면 부모노드의 index가 자식노드의 index /2 이고, 반대로 부모노드의 index *2, index*2+1이 자식노드의 index인 점을 이용하면 정말 간단하게 힙을 구현할 수 있다. 그리고 데이터를 넣을 때도 가장 마지막 index를 체크해주면 되는 것이기 때문에 정말 문제가 간단해진다. 

 

<최종 코드>

#include<iostream>

using namespace std;


int arr[100001] = { 0 };

void insert(int data, int *count)
{
	arr[++(*count)] = data;

	for (int i = (*count);i > 1; i /= 2)
	{
		if (arr[i] < arr[i / 2])
		{
			int temp = arr[i];
			arr[i] = arr[i/2];
			arr[i / 2] = temp;
		}
	}
}

void delete_heap(int * count)
{
	cout << arr[1] << "\n";

	arr[1] = arr[(*count)];
	arr[(*count)] = 0;
	(*count)--;
	
	for (int i = 1; (i <= (*count/ 2)) && (i*2+1 <= 100001);)
	{
		
		if ((arr[i * 2 + 1] == 0))
		{
			if(arr[i] >= arr[i * 2])
			{ 
				int temp = arr[i];
				arr[i] = arr[i * 2];
				arr[i * 2] = temp;
				i = i * 2;
			}

			break;
		}

		if ((arr[i] > arr[i * 2])) //i > i*2
		{
			if (arr[i * 2] < arr[i * 2 + 1]) // i > i*2+1 > i*2
			{
				int temp = arr[i];
				arr[i] = arr[i * 2];
				arr[i * 2] = temp;
				i = i * 2;
			}
			else // i > i * 2 > i * 2 + 1
			{
				int temp = arr[i];
				arr[i] = arr[i * 2 + 1];
				arr[i * 2 + 1] = temp;
				i = (i * 2 + 1);
			}

		}
		else if (arr[i] > arr[i * 2 +1]) { // i * 2 > i > i *2 +1 
			int temp = arr[i];
			arr[i] = arr[i * 2 + 1];
			arr[i * 2 + 1] = temp;
			i = (i * 2 + 1);
		}
		else // ? > ? > i
			break;
	}

}

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

	int number, repeat;
	int count = 0;
	cin >> repeat;

	for (int i = 0; i < repeat; i++)
	{
		cin >> number;
		if (number == 0)
		{
			if (count == 0)
				cout << 0 << "\n";
			else
				delete_heap(&count);
			
		}
		else
		{
			insert(number, &count);

		}
	}
	return 0;
}

풀 때 자꾸 0 (빈 노드) 이 출력되어서 조금 삽질을 했다. 노드가 비어있는지 확인하는 과정을 넣어주니 해결되었다. 삽질의 가장 큰 이유가 && 연산자를 너무 남발했다. 그러다보니 자꾸 조건이 빠지게 되어서 모든 케이스에서 안돌아갔고 결국 코드를 다 다시 풀었더니 성공했다. 

 

이번 문제를 풀면서 더욱더 개념이 중요하다는 것을 깨달았다. 솔직히 힙을 배운지 얼마 안된 시점이었다면, 바로 배열을 이용해 만들었을텐데 멍청하게 구조체로 시작했다. 조금만 더 생각하면 더 간단하게 풀 수 있었을텐데.. 다음부터는 조금 더 생각하고 접근을 시작해야겠다 .