C++ 백준 1927 최소 힙

백준 1927

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

1927번: 최소 힙

풀이전 나의 생각

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

이 연산을 최소 힙 자료구조를 사용하여 진행해야 한다.

 

조건

- N(1 ≤ N ≤ 100,000)

- x는 2^31보다 작은 자연수 또는 0

 

과정

이 문제에서 요구하는 것은 최소 힙을 사용하여 최솟값 구하는 것이다.
그러면 최소 힙을 사용하는 자료구조 중 최대나 최소를 구할 수 있는
것을 사용하면 되는데 그것이 바로 우선순위 큐다.

우선순위 큐를 아무 조건없이 사용한다면 항상 최대를 반환하기 때문에
비교값을 추가하여 내림차순으로 변경 후, 주어지는 x에 따라
우선순위 큐에 값을 넣고, 출력하도록 구현하면 된다.

 

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <string.h>
#include <limits.h>
#include <cstdio>
#include <map>
#include <deque>

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	//내림차순 
	priority_queue<int, vector<int>, greater<int>> pq;

	int N;
	cin >> N;
	
	for (int i = 0; i < N; i++)
	{
		int x;
		cin >> x;

		//x의 값이 0이 아니라면 우선순위 큐에 삽입
		if (x != 0)
		{
			pq.push(x);
		}
		//0이라면
		else
		{
			//큐가 비어있다면 0출력
			if (pq.empty())
			{
				cout << "0" << "\n";
			}
			//아니라면 최소를 출력하고 값을 제거
			else
			{
				cout << pq.top() << "\n";
				pq.pop();
			}			
		}
	}
}