[자료구조] 백준 11279번: 최대 힙 (C++), 우선 순위 큐 사용

[틀렸던 코드]

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

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int n;
	cin >> n;
	vector<int> arr;
	vector<int> answer;
	for (int i = 0; i < n; i++) {
		int idx;
		cin >> idx;
		if (idx == 0) {
			sort(arr.begin(), arr.end());
			if (!arr.empty()) {
				answer.push_back(arr.back());
				arr.pop_back();
			}
			else {
				answer.push_back(0);
			}
		}
		else {
		arr.push_back(idx);
		}
	}

	for (int i = 0; i < answer.size(); i++) {
		cout << answer[i] << '\n';
	}

	return 0;
}

시간제한은 1초이다. 하지만 최대로 주어지는 연산의 수가 100,000이 될 수가 있다. 이럴 경우 50,000을 push 하고 나머지 50,000이 0이 나와 정렬을 해야 할 경우 for(100,000) x sort(50,000 x log(50,000))이 되어 시간 초과를 일으킨다.

---

우선순위 큐를 사용하여야 한다.

(+개념)
https://draw-code-boy.tistory.com/47

[자료구조] 우선순위 큐 (Priority Queue) 개념, C++ STL

우선순위 큐는 넣을 때 즉각적으로 정렬이 되고, 한 번 넣을 때 시간 복잡도가 O(log N)이기 때문에 시간에 부담 없게 문제를 풀 수 있다.

최대 힙이기 때문에 맨 앞의 원소가 제일 큰 값이 되어야 한다.

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

int main() {
	int n;
	cin >> n;
	priority_queue<int> q;
	vector<int> answer;

	for (int i = 0; i < n; i++) {
		int idx;
		cin >> idx;
		if (idx == 0) {
			if (q.empty()) {
				answer.push_back(0);
			}
			else {
				answer.push_back(q.top());
				q.pop();
			}
		}
		else {
			q.push(idx);
		}
	}

	for (int i = 0; i < answer.size(); i++) {
		cout << answer[i] << '\n';
	}

	return 0;
}

---

힙과 우선순위 큐는 밀접한 연관이 있다.

이번 문제 말고도 우선순위 큐가 어떻게 구현이 되어있고, 돌아가는 지를 살펴보면 힙과 밀접한 연관이 있다는 것을 알 수 있다. (첨부한 개념 글에 살짝 설명을 해두었다.)

---

우선순위 큐 compare 방법

https://draw-code-boy.tistory.com/134

[자료구조] 우선순위 큐, 비교 연산자 (C++)