글 읽기 - C언어 힙 정렬 이용했는데 틀렸다고 나옵니다.

jja08111 4년 전 0

데이터를 직접 넣어보면 값은 잘 나오는것 같으나 틀렸다고 나오네요.

어디가 문제인지 알려주시면 감사하겠습니다.

#include <stdio.h>
#define MAX 1000000

void Swap(int *a, int *b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

void ReadData(int *arrData, int *ptrNum)
{
	scanf("%d",ptrNum);
	for(int i=0;i<*ptrNum;i++)
		scanf("%d",&arrData[i]);
}

void Heapify(int *arrData, int root, int size)
{
	int child=root*2+1;
	if(arrData[child]<arrData[child+1])
		child++;
	if(arrData[root]<arrData[child] && child<size)
	{
		Swap(&arrData[root],&arrData[child]);
		if(child*2+1<size) // 런타임 에러가 나와서 넣었습니다.
			Heapify(arrData, child, size);
	}
}

void BuildHeap(int *arrData, int size)
{
	for(int i=size/2-1;i>=0;i--)
		Heapify(arrData, i, size);
}

void HeapSort(int *arrData, int size)
{
	BuildHeap(arrData,size);
	for(int i=size-1;i>=0;i--)
	{
		Swap(&arrData[0],&arrData[i]);
		Heapify(arrData, 0,i);
	}
}

int main(void)
{
	int arrData[MAX], size, i;
	
	ReadData(arrData, &size);
	HeapSort(arrData, size);
	
	for(i=0;i<size;i++)
		printf("%d\n",arrData[i]);
		
	return 0;
}

jja08111 4년 전 0

21번째 줄 if문 조건에서

if(arrData[child]<arrData[child+1] && child<size-1)

뒷부분 child<size-1 조건이 빠졌습니다.

이유는 parent node가 child node를 좌측 한개만 가지고 있는 경우가 있기 때문입니다.

이전에는

입력시

으로 출력되었으나

현재는

으로 정상적으로 결과가 나옵니다.

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

문제

문제

출처

ICPC

C언어 힙 정렬 이용했는데 틀렸다고 나옵니다.

jja08111 4년 전 0

jja08111 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말