[BAEKJOON] 1927번 최소 힙

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

1927번: 최소 힙

문제조건

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

우선 입/출력이 많이 일어나기 때문에 입출력에 대해서 시간을 줄여줘야한다.

다들 많이 알고 있는 단축 코드이다.

ios::sync_with_stdio(false);
cin.tie(0);

 

https://dingcoding.tistory.com/62

ios::sync_with_stdio(false), cin.tie(0) 쓰는 이유, 백준 시간초과 해결

이 글에서 자세히 다루니, 나는 여기까지만 말하고 문제를 보겠다.

문제는 정말 무난했다. 그냥 priority_queue를 쓸 줄아냐고 물어보는 문제였다.

다만 여기선 priority_queue<int, vector<int>, greater<int>> 를 사용해서 우선순위의 큐의 top이 가장 작은 수가 오도록 최소힙으로 바꿔줘야 한다는 점이다. 

• ,int : 자료형
• vector<int> : 컨테이너형(구현체)
• greater<int> : 비교연산자

물론 비교연산자를 구조체를 만들고, operator 함수를 따로 구현해서, 커스터마이징 하는 방법도 있다.

그런다음 문제의 조건에 맞게 구현만 한다면 바로 풀린다!

#include <iostream>
#include <queue>
using namespace std;
priority_queue<int, vector<int>, greater<int>> pq;

int n;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
		if (x == 0) {
			if (pq.empty()) cout << 0 << '\n';
			else {
				cout << pq.top() << '\n';
				pq.pop();
			}
		}
		else pq.push(x);
		
		
	}
}

쉬운 문제였다.