BOJ 1927: 최소 힙

#BOJ 1927: 최소 힙

1927번: 최소 힙

#풀이

문제를 읽어보면 항상 최솟값만 출력하고 출력한 최솟값을 배열에서 지운다.

이 것을 통해 최소 힙을 사용하면 간단하게 해결할 수 있다는 것을 알 수 있다.

 

힙을 사용하는 stl중에서는 priority_queue가 있다. 하지만 우선순위 큐는 최대 힙이 디폴드로 되어 있어 따로 비교함수를 만들거나 다른 방법을 사용해서 최소 힙으로 변경한 뒤에 사용해야 한다.

 

priority_queue<int, vector<int>, cmp> 또는 priority_queue<int, vector<int>, greater<int>> 를 사용해야 한다.

 

또한 sort() 함수에서 사용했던 비교함수가 아닌 클래스로 정의한 다음 operator() 로 연산자를 만들어야한다.

 

#코드

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
class cmp {
public:
	bool operator() (int a, int b) {
		if (a > b) return true ; // true b가 앞으로 감 
		return false;
	}
};
priority_queue<int, vector<int>,cmp > q;
int n;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
		if (x == 0)
		{
			if (q.empty()) {
				cout << 0 << '\n';
			}
			else
			{
				cout << q.top() << '\n';
				q.pop();
			}
			
		}
		else {
			q.push(x);
		}
	}

	return 0;
}