[백준] 1927번 최소 힙

 

 

문제

소스코드

#include<iostream>
#include<queue>
#include<vector>
constexpr int MAX_NUMBER = 100001;

int main() {
	std::priority_queue<int, std::vector<int>, std::greater<>> queue;
	std::vector<int>read_v;
	read_v.reserve(MAX_NUMBER);
	int X;
	std::cin >> X;
	int number;
	for (int i = 0; i < X; ++i) {
		std::cin >> number;
		if (number == 0) {
			if (queue.empty() == false) {
				read_v.emplace_back(queue.top());
				queue.pop();
			}
			else
				read_v.emplace_back(0);
		}
		else {
		queue.emplace(number);
		}
	}
	for (const auto i : read_v)
		std::cout << i << "\n";
}

 

후기

이 문제를 풀기 위해서는 두 가지를 해결해야 한다.

1. 자료구조에 최솟값을 출력할 수 있어야 한다.

    STL 컨테이너 중 하나인 우선순위 큐를 이용해서 가장 작은 값이 위로 앞에 올 수 있도록 오름차순 정렬을 하였다.

 

2. 0이 입력되면 가장 작은 값이 출력되거나 0이 나와야 한다.

   우선순위 큐의 메서드 중 하나인 empty()를 사용하여 큐가 비어있는지 확인 후 비어 있다면 0을 비어있지 않다면  

   해당 큐에서 가장 작은 값을 벡터에 넣어 출력할 수 있게 풀었다.

 

전에 풀었던 최대 힙과 다르게 이번에는 우선순위 큐를 이용해서 풀었다. 라이브러리를 사용하는 만큼 빠르게 구현할 수 있었다.

 

 

출처 및 레퍼런스

문제 링크:https://www.acmicpc.net/problem/1927

 

관련 자료구조 글

[백준] 11279번 최대 힙

우선순위 큐(Priority Queue)