[C++] 백준 1927 : 최소 힙

문제

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

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

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

입력

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

출력

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

---

문제를 정리하자면,

우선 input으로 데이터 x를 n번 입력받습니다.

- 이 때, x가 자연수일 때는 배열에 x를 집어넣고,

- x가 0일 때는 배열의 최소 값을 출력한 뒤 배열에서 해당 값을 삭제합니다.

- x가 0일 때, 배열이 비어있다면 0을 출력합니다.

 

우선 문제의 풀이를 들어가기 전, Minheap(최소 힙)이란 무엇일까요?

그림에서 볼 수 있듯, Minheap은 트리 구조에서 부모의 값이 자식의 값보다 작은 상태입니다.

이 문제에서 배열의 최소 값을 출력 및 삭제하기 위해 정렬할 때 바로 Minheap의 구조가 쓰이죠.

---

문제의 제목이 최소 힙인 만큼 Minheap sort를 이용하려 했으나 구현에 실패했습니다.

아래의 접은 글은 Minheap sort를 사용한 실패한 코드입니다.

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

void swap(vector<int>& heap, int i, int j) {
	int tmp = heap[i];
	heap[i] = heap[j];
	heap[j] = tmp;
}

void minHeapify(vector<int>& a, int h, int m) {
	int v = a[h];
	int i = h * 2;

	while (i <= m) {
		if (i < m && a[i] > a[i + 1])
			i = i + 1;

		if (v <= a[i])
			break;
		else {
			a[i / 2] = a[i];
			i = i * 2;
		}
	}
	a[i / 2] = v;
}

void minHeapSort(vector<int>& a, int n) {
	for (int i = n / 2; i >= 1; i--) {
		minHeapify(a, i, n);
	}
	for (int i = n; i >= 2; i--) {
		swap(a, 1, i);
		minHeapify(a, 1, i - 1);
	}
}

int main() {
	int n, x;
	cin >> n;
	vector<int> arr;
	int size = 0;

	for (int i = 0; i < n; i++)
	{
		cin >> x;
		if (x == 0) { // 0을 입력했을 때
			if (size == 0) {
				cout << "0" << endl; // 빈 배열이면 0 출력
			}
			else { // 배열에 값이 존재할 때
				minHeapSort(arr, size); // HeapSort 후
				cout << arr[0] << endl; // 최소 값 출력
			}	
		}
		else {
			if (x < 0) { // error handling
				cout << "input value error!" << endl;
				break;
			}
			else {
				arr.push_back(x); // 0, 음수 아닌 값은 배열에 삽입
				size++;
			}
		}
	}
	return 0;
}

정수형 벡터 배열인 arr을 선언한 뒤, 배열에 데이터가 들어있을 때 0을 입력하면 최소의 값을 출력합니다.

최소값을 출력하기 전 배열을 minHeapSort 해준 뒤 최소의 값이 들어있는 arr[0]을 출력하는데,

디버깅 결과 이 때 minHeapSort 함수로 넘어가는 부분에서 인덱스 참조 오류가 발생하였습니다.

조금만 더 수정하면 구현이 가능할 텐데, pq를 사용하면 된다고 하여 포기한 코드입니다.

 

이 문제는 priority queue(우선순위 큐)를 사용하여 풀이하는 것이 코드가 간단하며 빠릅니다.

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

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

	priority_queue <int, vector<int>, greater<int>> pq; 
	// 비교함수로 greater<int>를 사용하여 올림차순 pq 선언
	int n;
	cin >> n; // n 선언 및 입력을 pq보다 일찍 선언하니 시간초과

	for (int i = 0; i < n; i++)
	{
		int x;
		cin >> x;
		if (x != 0) {
			if (x > 0) {
				pq.push(x); // 0, 음수 아닌 값은 pq에 삽입
			}
			else { // error handling
				cout << "input value error!" << endl;
				break;
			}
		}
		else { // 0을 입력했을 때
			if (pq.empty())
				cout << "0\n"; // 빈 배열이면 0 출력
			else { // 배열에 값이 존재할 때
				cout << pq.top() << '\n'; // 최소 값 출력
				pq.pop(); // 최소 값 pop
			}
		}
	}
	return 0;
}

priority queue를 선언하는 방식은 크게 두 가지로 나뉩니다.

1. priority_queue <자료형> 변수이름;
2. priority_queue <자료형, container, 비교함수> 변수이름;

1번과 같이 pq를 선언하면 내림차순 pq, 즉 Maxheap 형태가 만들어지며,

2번과 같이 선언하면 올림차순, 절대값 등 여러 구조의 pq를 만들 수 있습니다.

 

이번 문제에서는 올림차순 pq, 즉 Minheap 구조가 필요한데,

이 경우 비교함수로 greater<int>가 필요합니다.

 

이후 데이터의 크기 n을 선언하고 입력받습니다.

이 때 사진과 같이 시간초과를 여러 번 맛봤는데,,,🤯🤯🤯

n을 먼저 입력받고 pq를 선언하는 부분을 반대로

pq를 먼저 선언한 뒤 n을 입력받는 방식으로 바꾸니 드디어 시간초과가 발생하지 않았습니다.

 

어쨌거나 pq 선언, n 입력이 끝났다면 이제 x를 입력받을 때입니다.

for 루프를 n번 돌면서 x를 n번 입력받는데, 이 때

- x가 자연수일 때 pq에 삽입 : push(x)

- x가 0일 때 배열의 최소 값을 출력 후 제거 : top(), pop()

- x가 0일 때 배열이 비어있다면 0을 출력 : empty()

priority queue의 멤버 함수들을 활용하여 코드를 작성했습니다.

 

위의 minHeapSort를 이용한 풀이는 계속 정렬을 해주고 인덱스를 신경써줘야 하는 반면,

priority queue를 사용한다면 자동으로 배열이 정렬되기 때문에 push, pop, top 등의 멤버 함수만 사용해주면 풀이가 끝나는 문제였습니다.