[백준/BOJ] 1927번 최소 힙 (C/C++)

백준 온라인 저지(BOJ) 1927번 최소 힙
https://www.acmicpc.net/problem/1927

1927번: 최소 힙

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

 

1. 문제

최소 힙 자료구조 작성
연산의 개수 N 은 최대 100,000개
각 연산으로 입력되는 정수 x 는 2^31 보다 작은 자연수 또는 0 (음수 X)
- x가 자연수인 경우 힙에 추가
- 0인 경우 최소 값을 출력하고 배열에서 제거 (배열이 빈 경우 0 출력)

 

2. 풀이

힙 구조에 대한 이해가 있다면 전혀 어려운 문제는 아닙니다.
특정 자료구조를 학습하셨다면 해당 자료구조에 익숙해질 때까지
마음에 드는 소스를 찾은 후 반복 구현하고 디버깅하면서 본인 것으로 만드는 과정이 필요합니다.

일반적인 힙 자료구조 구현 코드이므로 추가 설명 없이 마치겠습니다.

 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif

#include <cstdio>

const int LM = 100000;
int h[LM + 5], hn;

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

void push(int v) {
	h[++hn] = v;

	for (int c = hn; c > 1; c >>= 1) {
		if (h[c] < h[c / 2]) swap(h[c], h[c / 2]);
		else break;
	}
}

int pop() {
	if (hn == 0) return 0; // 배열이 빈 경우 0 출력

	int v = h[1];
	swap(h[1], h[hn--]);

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

		if (h[c] < h[c / 2]) swap(h[c], h[c / 2]);
		else break;
	}
	return v;
}

int main() {
	int N, x;
	scanf("%d", &N);

	for (int i = 0; i < N; ++i) {
		scanf("%d", &x);
		if (x > 0) push(x);
		else printf("%d\n", pop());
	}
	return 0;
}