알고리즘/기타

[C++] 백준 1927번 최소힙

키베이루 2022. 5. 23. 23:34

 

1) 문제설명

백준 Online Judge 1927번 최소힙

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

 

1927번: 최소 힙

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

www.acmicpc.net

 

2) 해결방법

O(n)의 시간을 맞춰야 하므로 우선순위 큐를 이용하여 구현한다.

 

3) 코드

#include<iostream>
#include<queue>
#include<deque>
#include<string.h>
#include<math.h>
#include<cmath>
#include<stack>
#include<algorithm>

using namespace std;

/*


*/
int main() {
	int n;
	priority_queue <int,vector<int>,greater<int>> pq;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int x;
		scanf("%d", &x);
		if (x != 0) {
			pq.push(x);
		}
		else {
			if (pq.empty()) {
				printf("0\n");
			}
			else {
				printf("%d\n", pq.top());
				pq.pop();
			}		
		}
	}
}

priority_queue<int ,vector<int>,greater<int>>를 써서 우선순위를 오름차순으로 한다.