글 읽기 - 최소힙 문제 어느 부분이 틀렸는지 모르겠습니다

sjsj0128 3년 전 0

예시 코드도 맞고 입력해보면 맞게 출력되는데

틀렸다고 나오네요,,,

어느부분이 잘못되었나요?

#include <iostream>
#define MAX 1000001
using namespace std;
typedef struct heap
{
	int arr[MAX];
	int size;
}Heap;

void Insert(Heap& hp, int input);
void Print_Delete(Heap& hp);

Heap heap{};

int main()
{
	int N;
	scanf("%d", &N);

	for (int i = 0; i < N; i++)
	{
		int input;
		scanf("%d", &input);

		if (input != 0)
			Insert(heap, input);
		else
			Print_Delete(heap);

	}
}

void Insert(Heap& hp, int input)
{
	// 현재 크기의 +1 인덱스에 위치
	int here = ++hp.size;

	// here가 루트노드이거나 부모의 값보다 입력값이 작으면
	// 루프를 빠져나온다.
	while ((here != 1) && (input < hp.arr[here / 2]))
	{
		// here위치에 부모의 값을 넣고
		hp.arr[here] = hp.arr[here / 2];
		// here을 부모의 위치로 옮긴다.
		here /= 2;
	}
	// 옆에 값과 비교
	if (here % 2 == 1 && here != 1)
	{
		if (hp.arr[here - 1] > input)
		{
			hp.arr[here] = hp.arr[here - 1];
			hp.arr[here - 1] = input;
			return;
		}
	}
	// here값에 입력값을 넣는다.
	hp.arr[here] = input;
}

void Print_Delete(Heap& hp)
{
	// 가장 작은값 -> 루트값을 빼고 출력한다.

	// 힙이 비어있을 경우
	if (hp.size == 0)
	{
		cout << "0\n";
		return;
	}
	// 루트노드의 값 저장
	int del = hp.arr[1];

	// 루트노드에 맨마지막 노드의 값 넣기
	hp.arr[1] = hp.arr[hp.size--];
	hp.arr[hp.size + 1] = 0;
	// 자식노드가 루트노드의 값보다 작으면 바꾸기 반복
	int parent = 1;
	int child;

	while (true)
	{
		child = parent * 2;
		// 오른쪽 자식이 더 작은 수 이면
		if ((child + 1 <= hp.size) && (hp.arr[child] > hp.arr[child + 1]))
			child++;

		// child보다 힙 사이즈가 작거나 부모값이 더 작으면 break;
		if ((child > hp.size )|| (hp.arr[child] > hp.arr[parent]))
			break;

		// 부모와 자식 값 바꾸기
		swap(hp.arr[parent], hp.arr[child]);
		parent = child;
	}

	cout << del << '\n';
}

kth001 3년 전 0

자식이 1개일 경우는 고려하지 않으셨네요?

while (true)
	{
		child = parent * 2;
		// 오른쪽 자식이 더 작은 수 이면
		if ((child + 1 <= hp.size) && (hp.arr[child] > hp.arr[child + 1]))
			child++;

		// child보다 힙 사이즈가 작거나 부모값이 더 작으면 break;
		if ((child > hp.size )|| (hp.arr[child] > hp.arr[parent]))
			break;

		// 부모와 자식 값 바꾸기
		swap(hp.arr[parent], hp.arr[child]);
		parent = child;
	}

sjsj0128 3년 전 0

if ((child + 1 <= hp.size)

이 부분이 자식이 한 개일 경우 입니다. 왼쪽 자식만 있을 경우는 child + 1이 힙의 사이즈보다 크니까요

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

문제

문제

출처

ICPC

최소힙 문제 어느 부분이 틀렸는지 모르겠습니다

sjsj0128 3년 전 0

kth001 3년 전 0

sjsj0128 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말