글 읽기 - c++ 최대힙 구현 시간초과 도움 부탁드립니다.

oh_hyerin 3년 전 0

안녕하세요.

벡터로 직접 최대힙을 구현해봤는데 어디가 왜 시간초과가 나는지 잘 모르겠습니다. ㅜㅜ

시간복잡도에 대한 개념이 아직 부족해서 그런건지 ,,,,,

도움 주시면 감사하겠습니다.

#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);
	}
}

wjdclgns12 3년 전 1

벡터에서 맨 앞 원소를 지우는 연산의 시간복잡도는 O(n)입니다.

oh_hyerin 3년 전 0

@wjdclgns12

아 그러면 현재 ERASE 때문에 시간복잡도가 O(n)이라서 시간초과가 나는거라고 이해해도 될까요?

벡터에서 맨 앞 원소를 지우는 거 제외하고 혹시 POP을 구현하는 방법이 있을까요?

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

c++ 최대힙 구현 시간초과 도움 부탁드립니다.

oh_hyerin 3년 전 0

wjdclgns12 3년 전 1

oh_hyerin 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말