백준 11279번 최대

데이터 구조 힙, 우선 순위 큐 및 욕심 많은 문제를 해결하기 위해 열심히 노력하고 있습니다. 먼저 최대 힙 문제를 해결했습니다.

힙은 우선순위 큐를 구현하기 위해 생성된 데이터 구조입니다. 힙은 이진 트리로 구성되며 배열 또는 목록으로 구현할 수 있습니다. 물론 이 문제는 힙을 구현할 필요가 없고 stl만 사용해도 충분하지만 저는 공부용으로 배열로 구현했습니다.

기본 최대 힙 개념을 살펴보겠습니다.

1. 상위 노드는 항상 하위 노드보다 큽니다.

2. 자식 노드 아래에서 작은 노드는 왼쪽에 있고 큰 노드는 오른쪽에 있습니다.

그러한 배열이 있다고 가정합니다.

이것을 나무로 만들면

하나

/\

3 6

/ \ /

5 9 8

그렇게 될 것입니다. 이런 이유로

부모 노드 인덱스 = 자식 노드 인덱스 / 2

자식 노드의 인덱스 = 부모 노드의 인덱스 * 2 또는 부모 노드의 인덱스 * 2 + 1

공식이 됩니다. 이 수식은 삽입 및 삭제 작업이 됩니다.

첫 번째 stl 답변 –

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
vector<int> answer;
int main() {
	priority_queue<int> pq;
	int cnt = 0;
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int tmp;
		cin >> tmp;
		if (tmp == 0) {
			if (!pq.empty()) {
				answer.push_back(pq.top());
				pq.pop();
			}
			else
				answer.push_back(0);
		}
		else {
			pq.push(tmp);
		}
	}
    for(auto a : answer)
        cout << a << '\n';
}

배열로 구현된 답변 –

#include <iostream>
#include <vector>
using namespace std;
vector<int> answer;
int heap_cnt = 0;
int Array(100001);
void swap(int *a, int *b){
	int t;
	t = *a;
	*a = *b;
	*b = t;
}

int size() {
	return heap_cnt;
}

void heap_push(int data) {
	Array(++heap_cnt) = data;
	int child = heap_cnt;
	int parents = child / 2;
	while (child > 1 && Array(parents) < Array(child)) {
		swap(&Array(parents), &Array(child));
		child = parents;
		parents = child / 2;
	}
}

void heap_pop() {
	int top = Array(1);
	swap(&Array(1), &Array(heap_cnt));
	heap_cnt--;

	int parants = 1;
	int child = parants * 2;
	if (child + 1 <= heap_cnt) {
		child = (Array(child) > Array(child + 1)) ? child : child + 1;
	}

	while (child <= heap_cnt && Array(parants) < Array(child)) {
		swap(&Array(parants), &Array(child));
		parants = child;
		child = child * 2;
		if (child + 1 <= heap_cnt) {
			child = (Array(child) > Array(child + 1)) ? child : child + 1;
		}
	}
	answer.push_back(top);
}

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    
	int n;
	cin >> n;

	for (int i = 0; i < n; i++) {
		int tmp;
		cin >> tmp;

		if (tmp == 0) {
			if (heap_cnt == 0)
				answer.push_back(0);
			else {
				heap_pop();
			}
		}
		else 	
			heap_push(tmp);
	}
	for (auto a : answer)
		cout << a << '\n';
}

시차가 나는 이유는 ios::를 붙이는 것과 붙이지 않는 것의 차이입니다.