글 읽기 - c언어 힙정렬 틀렸습니다.

hsh5541 3년 전 0

많은 케이스를 시도해봤을 때 잘 작동했는데 틀렸습니다가 뜨네요.. 반례가 있을까요?

#include <stdio.h>
#define HEAP_LEN 1000001

typedef struct _heap{
	int heapArr[HEAP_LEN];
	int numOfData;
} Heap;

void HInit(Heap * ph)
{
	ph->numOfData = 0;
}

int GetParentIdx(int idx) { return idx/2; }
int GetLChildIdx(int idx) { return idx*2; }
int GetRChildIdx(int idx) { return idx*2+1; }
int GetHiPriChildIdx(Heap * ph, int idx)
{
		if(GetLChildIdx(idx) > ph->numOfData)
			return 0;
		else if(GetLChildIdx(idx) == ph->numOfData)
			return GetLChildIdx(idx);
		else
		{
			if(ph->heapArr[GetLChildIdx(idx)] > ph->heapArr[GetRChildIdx(idx)])
				return GetRChildIdx(idx);
			else
				return GetLChildIdx(idx);
		}
}

void HInsert(Heap * ph, int data)
{
	int idx = ph->numOfData+1;
	
	while(idx != 1)
	{
		if(data < ph->heapArr[GetParentIdx(idx)])
		{
			ph->heapArr[idx] = ph->heapArr[GetParentIdx(idx)];
			idx = GetParentIdx(idx);
		}
		else
			break;
	}
	
	ph->heapArr[idx] = data;
	(ph->numOfData)++;
}

int HDelete(Heap * ph)
{
	int rdata = ph->heapArr[1];
	int LastData = ph->heapArr[ph->numOfData];
	
	int ParentIdx = 1;
	int ChildIdx;
	
	while(ChildIdx = GetHiPriChildIdx(ph, ParentIdx))
	{
		if(LastData > ChildIdx)
		{
			ph->heapArr[ParentIdx] = ph->heapArr[ChildIdx];
			ParentIdx = ChildIdx;
		}
		else
			break;
	}
	ph->heapArr[ParentIdx] = LastData;
	(ph->numOfData)--;
	return rdata;
}

int main()
{
	int N;
	scanf("%d", &N);
	
	Heap h;
	HInit(&h);
	
	for(int i=0; i<N; i++)
	{
		int inputNum;
		scanf("%d", &inputNum);
		
		HInsert(&h, inputNum);
	}
	for(int i=0; i<N; i++)
		printf("%d\n", HDelete(&h));
	
	return 0;
}

nahwasa 3년 전 1

넹 있죠!

3
0
0
1
예상출력 :
0
0
1
출력 :
0
1
0

hsh5541 3년 전 1

감사합니다. 어디가 틀렸는지 바로 알겠네요 ㅎㅎ;; 감사합니다!!

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

문제

문제

출처

ICPC

c언어 힙정렬 틀렸습니다.

hsh5541 3년 전 0

nahwasa 3년 전 1

hsh5541 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말