[백준] 1927번: 최소 힙 C++로 풀어보기

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

1927번: 최소 힙

 

1927번 설명

생각

사실 이 문제의 목적은 직접 최소 힙을 구현하라는 것이지만,

C++에서는 STL priority_queue가 있어서 최소 힙을 직접 구현하지 않고도 문제를 풀 수 있다.

C++에서 최소 힙을 사용하려면 아래와 같은 방식으로 선언해야한다.

priority_queue<int, vector<int>, greater<int>> pq;

 

코드

#include <bits/stdc++.h>
using namespace std;
priority_queue<int, vector<int>, greater<int>> pq; // 최소 힙


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

	int n; // 연산의 개수 n
	cin >> n;

	while (n--) {
		int x;
		cin >> x;
		
		if (x == 0) { // x가 0이라면
			if (pq.empty()) { // 배열이 비어있을 경우
				cout << 0 << '\n'; // 0 출력
			}
			else {
				cout << pq.top() << '\n'; // 배열에서 가장 작은 값 출력
				pq.pop(); // 그리고 그 값을 배열에서 제거
			}
			
		}

		else { // x가 0이 아니라면
			pq.push(x); // 배열에 x 삽입
		}
	}
}

 

결과

1927번 결과

너무 날로 먹었나라는 생각이 들었다. 라이브러리의 힘을 느낄 수 있었다.

이와는 별개로 따로 힙을 구현하는 방법을 공부해놓는 것이 좋을 것 같다.