우선순위 큐 - 백준 11279번 최대 힙 & 백준 1927번 최소 힙

www.acmicpc.net/problem/11279

11279번: 최대 힙

실패 IDEA

최대 힙 : 부모노드 > 자식노드다.

힙 구현하는 법을 그냥 외우고있어서 이거에 따라서 코드를 짜봤다.

힙 구현하는 법은 여기 👉 blahblahlab.tistory.com/33  

#include <iostream>
#include <vector>
#include<algorithm>
using namespace std;

int n;
vector<int>heap;

void make_heap(int idx, int end) {
	int temp = idx;
	int left = 2 * idx + 1, right = 2 * idx + 2;
	if (left < end && heap[left] > heap[temp]) temp = left; 
	if (right < end && heap[right] > heap[temp]) temp = right;
	if (idx != temp) {
		swap(heap[idx], heap[temp]);
		make_heap(temp, end);
	}
	return;
}

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		int num;
		scanf("%d", &num);
		if (num == 0) {
			if (heap.empty()) printf("0\n");
			else {
			//정렬 후
				int size = heap.size();
				for (int i = size/ 2 - 1; i >= 0; i--) {
					make_heap(i, size);
				}
			// 맨 위 원소 0번째 출력
				printf("%d\n", heap[0]);
				heap.erase(heap.begin());
			}
		}
		else heap.push_back(num);
	}
}

시간초과가 난다 . 이유는 아직 잘 모르겠다 ㅜㅜ 

 

성공 코드 

그래서 그냥 우선순위큐 PRIORITY_QUEUE를 이용해 구현했다. 

최대 힙은 내림차순이어야하므로 less<int> 를 써준다. 

#include <iostream>
#include <queue>
#include<algorithm>
using namespace std;

int n;
priority_queue<int, vector<int>, less<int>>pq;

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		int num;
		scanf("%d", &num);
		if (num == 0) {
			if (pq.empty()) printf("0\n");
			else {
				printf("%d\n", pq.top());
				pq.pop();
			}
		}
		else pq.push(num);
		}
	}

 

최소 힙은 올림차순이어야하므로 greater<int>를 사용한다. 

#include <iostream>
#include <queue>
#include<algorithm>
using namespace std;

int n;
priority_queue<int, vector<int>, greater<int>>pq;

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		int num;
		scanf("%d", &num);
		if (num == 0) {
			if (pq.empty()) printf("0\n");
			else {
				printf("%d\n", pq.top());
				pq.pop();
			}
		}
		else pq.push(num);
		}
	}