백준 C++ | #14 BOJ1927 최소 힙 C++ 문제 풀이

1927번: 최소 힙 (acmicpc.net)

1927번: 최소 힙

 

문제 자체는 간단하다. 

x개의 정수를 받아서

x가 자연수일 때에는 x를 배열에 저장해두고, x가 0일 때는 배열의 최댓값을 출력한 뒤에 그 값을 삭제해주면 된다. 

 

처음에는 최소 힙을 사용하지 않고 벡터를 이용해서 구현했다. 

그랬더니 시간 초과가 발생해서 queue의 priority queue를 이용해서 구현했으나 그래도 시간초과가 나서

결국 std::cin, cout 대신 scanf, printf를 이용해서 입출력을 만들었더니 그제야 제 시간에 통과할 수 있었다. 

 

[참고] 우선순위 큐(priority_queue) 최대 힙, 최소 힙 in C++ - (2) (velog.io)

[참고] (C++) - cout,cin 실행 속도 높이기(시간초과 해결법) (tistory.com)

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <stdio.h>

int main() {
	// 정답 저장소 
	std::vector<int> answer;

	// 연산의 개수 n
	int n;
	scanf("%d", &n);

	std::priority_queue<int> pqueue;

	// n개의 줄에서 연산을 수행하기
	int x;
	for (int i = 0; i < n; i++) {
		scanf("%d", &x);
		if (x > 0) {
			pqueue.push(-x);
		}
		else if (x == 0) {
			if (pqueue.empty()) {
				answer.push_back(0);
			}
			else {
				// 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거하기
				answer.push_back(-pqueue.top());
				pqueue.pop();
			}
		}
	}

	std::vector<int>::iterator iter;
	for (iter = answer.begin(); iter != answer.end(); iter++) {
		printf("%d\n", *iter);
	}
	return 0;
}