글 읽기 - 2751번 heap sort로 풀었는데 계속 시간초과나네요ㅠㅠㅠ

areumchoi19 7년 전 0

extract_min에서 시간초과가 나는 것 같은데..(계속 min heapify를 하다보니 ㅠㅠ)

어떻게 수정하면좋을까요ㅠㅠㅠ

#include<stdio.h>
#include<stdlib.h>
void Min_Heapify(int n);
void BuildMinHeap(int i, int n);
void extract_min(int n, int k);
static int *quick;
int main(void){
	int i,test_num;
	scanf("%d",&test_num);
	quick = (int*)malloc(sizeof(int)*test_num);

	for(i=0;i<test_num;i++){
		scanf("%d",&quick[i]);
	}
	extract_min(test_num,0);
}
void extract_min(int n,int k){
	if(n==1){
		printf("%d\n",quick[0]);
	}else{
		Min_Heapify(n);
		printf("%d\n",quick[0]);
		quick[0]=quick[n-1];
		extract_min(--n,++k);
	}
}
void Min_Heapify(int n){
	int i;
	for(i=n/2-1;i>=0;i--){
		BuildMinHeap(i,n);
	}
}
void BuildMinHeap(int i,int n){
	int left_child = i*2+1,right_child = i*2+2,smallest = i,temp;
	if(left_child<n&&quick[left_child]<quick[smallest]){
		smallest = left_child;
	}
	if(right_child<n&&quick[right_child]<quick[smallest]){
		smallest = right_child;
	}
	if(smallest!=i){
		temp = quick[i];
		quick[i] = quick[smallest];
		quick[smallest] = temp;
		BuildMinHeap(smallest,n);
	}
}

hun222y 7년 전 0

그냥 STL sort 써도 통과하긴 해용

nohhans 7년 전 0

이문제가 nlogn이면 풀리는 문제인데 힙정렬이면 nlogn이라 맞는데 어딘가 꼬였나봐요..
stl의 퀵소트나

머지소트로 구현하시면 잘통과되실거에요...ㅜㅜ

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

문제

문제

출처

ICPC

2751번 heap sort로 풀었는데 계속 시간초과나네요ㅠㅠㅠ

areumchoi19 7년 전 0

hun222y 7년 전 0

nohhans 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말