글 읽기 - 아무리 생각해도 틀린게 없습니다......

thoon916 2년 전 1

아무리 반례를 생각하고 대입해봐도 답이 너무 정상적으로 나옵니다 도대체 어디가 틀린지 모르겠습니다. 반례나 틀린부분 좀 찾아주세요

#include <stdio.h>

#define ROOT 1

int heap[100001];

int last = 0;

int SmallOne(int a, int b)
{
	return heap[a] < heap[b] ? a : b;
}

void InsertToHeap(int v)
{
	if (last == 0)
	{
		heap[++last] = v;
	}
	else
	{
		heap[++last] = v;
		int me = last, parent = last / 2;

		while (heap[parent] > heap[me])
		{
			int temp;
			temp = heap[me];
			heap[me] = heap[parent];
			heap[parent] = temp;

			me = parent;
			parent = me / 2;
		}
	}
	return;

}

void DeleteFromHeap()
{
	int result = heap[ROOT];

	if (last == 0)
	{
		printf("0\n");
		return;
	}
	else if (last == 1)
	{
		printf("%d\n", result);
		last--;
		return;
	}
	else
	{
		heap[ROOT] = heap[last];
		heap[last] = 0;
		last--;

		int me = ROOT;
		int leftchild = me * 2, rightchild = me * 2 + 1;

		int smallchild = 0;

		while (1)
		{
			if (leftchild > last)
			{
				break;
			}
			else if (leftchild == last)
			{
				smallchild = SmallOne(me, leftchild);
				if (me == smallchild)
				{
					break;
				}
			}
			else
			{
				smallchild = SmallOne(leftchild, rightchild);
			}
			int temp = heap[me];
			heap[me] = heap[smallchild];
			heap[smallchild] = temp;

			me = smallchild;
			leftchild = me * 2;
			rightchild = me * 2 + 1;
		}
	}

	printf("%d\n", result);
}



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

	int x;

	for (int i = 0; i < N; i++)
	{
		scanf("%d", &x);
		if (x > 0)
		{
			InsertToHeap(x);
		}
		else
		{
			DeleteFromHeap();
		}
	}
}

euphoric_n 2년 전 4

heap에서 원소를 삭제하는 부분에서 잘못된 점이 있습니다.

우선 heap[ROOT] 값을 저장해두고 heap[last]에 있는 값을 heap[ROOT]로 옮긴 뒤 자리를 찾아주는 방식인데요

만약 왼쪽 자녀의 인덱스가 last 보다 크다면 당연히 더이상 교환하지 않고 멈춥니다.

자녀노드가 왼쪽에만 있는 경우에는 왼쪽자녀만 비교를 하면 되고

자녀노드가 양쪽에 있다면 그 중에서 작은 값을 선택합니다.

하지만 heap[smallchild]값이 heap[me]보다 클 수도 있습니다.

이런 경우에는 탐색을 종료해야겠지요.

thoon916 2년 전 0

그걸 까먹고 있었네요 ㅎㅎ 감사합니다

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

문제

문제

출처

ICPC

아무리 생각해도 틀린게 없습니다......

thoon916 2년 전 1

euphoric_n 2년 전 4

thoon916 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말