[백준/BOJ] 11279번 최대 힙 (C/C++)

백준 온라인 저지(BOJ) 11279번 최대 힙

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

* 사용언어 : C언어, C++

 

1. 문제

최대 100,000번 연산(x = 0 또는 자연수)이 주어짐

x가 자연수이면 배열에 값을 넣고, 0이면 배열에서 가장 큰 값을 뽑아 출력

배열이 비어있는 경우 0을 출력

 

2. 풀이

우선순위 큐(Priority Queue, 이하 PQ) 분류에 해당되는 첫 번째 문제입니다.

 

일반적인 Queue는 선입선출(First In First Out, FIFO)로 Data를 넣고 빼지만,

PQ는 이름 그대로 우선순위가 가장 높은 Data가 먼저 나와야 합니다.

이 문제는 가장 큰 값이 가장 높은 우선순위를 가지므로 최대 Heap으로 구현합니다.

 

Heap은 PQ를 구현하기 위해 사용하는 효율적인 방식입니다.

Heap은 완전이진트리 형태로 구성되는데 굳이 node 형태로 구현할 필요는 없고,

1차원 배열을 선언한 뒤 아래 성질을 활용하여 구현합니다.

• 왼쪽 노드의 index = 부모 노드의 index * 2
• 오른쪽 노드의 index = 부모 노드의 index * 2 + 1

 

Heap은 여러 가지 방식으로 구현할 수 있는데 이 문제는 1 base + swap 형태로 풀어보았습니다.

참고로 0 base를 쓰면 노드 처리가 복잡해기 때문에, 1 base로 구현하는 것을 추천드립니다.

 

이후에 다른 문제에서 no swap 버전을 구현해보겠습니다.

나머지 부분은 아래 코드로 설명 대체하겠습니다.

 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
11279_최대 힙
1500KB	20ms
*/
#include <cstdio>

const int LM = 100001; // 1 base
int h[LM], hn, c;

void swap(int &a, int &b) {
	int t = a;
	a = b;
	b = t;
}

void push(int v) {
	h[++hn] = v;
	for (c = hn; c > 1; c >>= 1) {
		if (h[c] > h[c >> 1]) swap(h[c], h[c >> 1]);
		else break;
	}
}

int pop() {
	if (hn == 0) return 0;

	int v = h[1];
	h[1] = h[hn--];
	for (c = 2; c <= hn; c <<= 1) {
		c += (c <= hn && h[c] < h[c + 1]);

		if (h[c] > h[c >> 1]) swap(h[c], h[c >> 1]);
		else break;
	}
	return v;
}

int main() {
	int n, x;

	scanf("%d", &n);
	while (n--) {
		scanf("%d", &x);
		if (x == 0) printf("%d\n", pop());
		else push(x);
	}
	return 0;
}