득이공간

[백준 C++] 1927 최소 힙 - 우선순위큐 본문

PS/알고리즘 문제풀이

[백준 C++] 1927 최소 힙 - 우선순위큐

쟁득 2024. 2. 15. 09:22
 

1927번: 최소 힙

첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0

www.acmicpc.net

#include <iostream>
#include <queue>
using namespace std;

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

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

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

		if (Input == 0)
		{
			if (MinHeap.empty())
			{
				cout << 0 << '\n';
			}
			else
			{
				cout << MinHeap.top() << '\n';
				MinHeap.pop();
			}
		}
		else
		{
			MinHeap.emplace(Input);
		}
	}
}

 

우선순위 큐 자료구조를 이용해서 푸는 문제입니다.

priority_queue<int>로 컨테이너를 선언하면 최대힙으로 생성되지만

priority_queue<int, vector<int>, greater<int>>로 선언하면 최소힙으로 생성됩니다.

최소힙으로 컨테이너를 생성한 후에 문제에서 제시하는 연산을 수행하는 프로그램을 작성하면 됩니다.