글 읽기 - 힙소트 시간초과 에러

jet1125 3년 전 0

예제 코드 돌려보면 잘 나오고 코드도 퀵소트가 아닌 힙소트로 짰는데 왜 시간초과가 뜨는지 모르겠습니다.

혹시 아시는 분 도와주세요ㅜㅜ

#include <iostream>
#include <cstdio>
#define SWAP(x, y, temp) ( (temp)=(x), (x)=(y), (y)=(temp) )

using namespace std;

void heapify(int arr[], int p, int heapsize){
	int left = p * 2;
	int right = p * 2 + 1;
	int largest;
	int temp;
	largest = p;
	if(left <= heapsize && arr[left-1] < arr[largest-1])

		largest = left;
	if(right <= heapsize && arr[right-1] < arr[largest-1])
		largest = right;
	
	if(largest != p)
		SWAP(arr[largest-1], arr[p-1], temp);
	
}

void build_heap(int arr[], int heapsize){
	
	for(int i = heapsize / 2; i > 0 ; i --){
		heapify(arr, i, heapsize);
		
	}


}

int main(){
	
	int N, temp;
	scanf("%d", &N);
	int * arr = nullptr;
	arr = new int[N];
	
	for(int i = 0; i < N; i ++){

		int k;
		scanf("%d", &k);
		arr[i] = k;
	}
	for(int i = N; i > 0; i --){
		
		build_heap(arr, i);
		printf("%d\n", arr[0]);
		SWAP(arr[0], arr[i - 1], temp);

		
	}
	
	delete[] arr;
	
	
	
}

djm03178 3년 전 0

build_heap은 힙이 아닌 상태의 배열을 힙으로 만드는 것이고, O(nlogn) 시간이 걸립니다. 다만, 이 경우 이미 '거의' 힙이 만들어진 상태에서 호출되기 때문에 O(n) 시간이 걸리고, 그래서 총 O(n^2) 시간이 걸립니다.

힙소트를 할 때 루트에 있는 원소를 제거한 뒤에는 heapify 하나면 힙 상태를 복구하는 데에 충분하고, 이를 O(logn) 시간에 할 수 있습니다.

djm03178 3년 전 0

또한 heapify의 구현도 잘못되었습니다. heapify는 지정된 원소가 더 위로 올라가거나 아래로 내려갈 필요가 없을 때까지 반복해서 원소를 이동해야 하는 것이고, 지금처럼 1회만 움직이는 것이 아닙니다.

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

문제

문제

출처

ICPC

힙소트 시간초과 에러

jet1125 3년 전 0

djm03178 3년 전 0

djm03178 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말