백준 1927 - 최소 힙

문제 설명

 

입력

첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. x는 231보다 작은 자연수 또는 0이고, 음의 정수는 입력으로 주어지지 않는다.

출력

입력에서 0이 주어진 횟수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 가장 작은 값을 출력하라고 한 경우에는 0을 출력하면 된다.

예제 입력 1 복사

9
0
12345678
1
2
0
0
0
0
32

예제 출력 1 복사

0
1
2
12345678
0

 

 

=> 최대힙의 반대로 최소힙문제입니다. 

=> queue 헤더안에 있는 우선순위 큐 자료형을 사용하면 되는 문제입니다. 

https://codingham.tistory.com/265

우선순위 큐 HEAP ||C++ STL priority queue

=> 위의 정리된 STL 사용법을 참조하면 됩니다. 

 

#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <iostream>
#include <queue>
#include <utility>

using namespace std;

int M;



int main()
{ 
	priority_queue<int> pq;
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	cin >> M;
	for (int i = 0; i < M; i++)
	{
		int tmp;
		cin >> tmp;

		if (tmp == 0)//max값 제거 
		{
			if (pq.empty()) cout << '0' << '\n';
			else
			{
				cout << pq.top() << '\n';
				pq.pop();
			}
		}
		else//삽입
		{
			pq.push(tmp);
		}
	}
	return 0;
}

 

실행화면