글 읽기 - 정말 긴 코드인데 봐주실 수 있나요?ㅠㅠ

his130 6년 전 0

heap 을 배열을 이용해서 구현해 봤습니다.

last 는 가장 말단 노드의 번호입니다.

root 노드는 1부터 시작하게 설정했습니다.

push 함수에서는

우선 절대값이 작으면 바꾸고, 절대값이 같으면 작은값으로 바꾸고

pop 함수에서는

l = 왼쪽자식 r=오른쪽자식 으로

왼쪽자식이 없을때, 오른쪽 자식이 없을때, 둘다 없을 때, 둘다 있을 때로 나눠서 풀었습니다.

예제 케이스는 모두 나오는데 어디에서 오류가 날까요...

#include<iostream>

using namespace std;
int N;
int heap[100001];
int last = 0;
void push(int n)
{
	heap[++last] = n;

	for (int i = last; i > 1; i /= 2)
	{
		int p = heap[i/2];
		int n = heap[i];
		
		if(abs(n)<abs(p))
		{
			swap(heap[i], heap[i/2]);
		}
		else
		{
			if (abs(n) == abs(p))
			{
				if (n < p)
				{
					swap(heap[i], heap[i/2]);
				}
				else
				{
					break;
				}
			}
			else
			{
				break;
			}
		}
	}

}
void pop()
{
	printf("%d\n", heap[1]);

	if (last == 0)
	{
		return;
	}

	swap(heap[last], heap[1]);
	heap[last--] = 0;

	for (int i = 1; i * 2 <= last;)
	{
		int p = heap[i];
		int l = heap[i * 2];
		int r = heap[i * 2 + 1];

		if (abs(p) < abs(l) && abs(p) < abs(r))
		{
			break;
		}
		else
		{
			if (l == 0 && r == 0)
			{
				break;
			}
			else if (l == 0 && r != 0)
			{
				if (abs(r) < abs(p))
				{
					swap(heap[i*2+1], heap[i]);
				}
				else 
				{
					if (abs(r) == abs(p))
					{
						if (r < p)
						{
							swap(heap[i*2+1], heap[i]);
						}
						else
						{
							break;
						}
					}
					else
					{
						break;
					}
				}

			}
			else if (l != 0 && r == 0)
			{
				if (abs(l) < abs(p))
				{
					swap(heap[i*2], heap[i]);
				}
				else
				{
					if (abs(l) == abs(p))
					{
						if (l < p)
						{
							swap(heap[i*2], heap[i]);
						}
						else
						{
							break;
						}
					}
					else
					{
						break;
					}
				}
			}
			else if (l != 0 && r != 0)
			{
				if (abs(l) < abs(r))
				{
					if (abs(l) < abs(p))
					{
						swap(heap[i*2], heap[i]);
					}
					else
					{
						if (abs(l) == abs(p))
						{
							if (l < p)
							{
								swap(heap[i*2], heap[i]);
							}
							else
							{
								break;
							}
						}
						else
						{
							break;
						}
					}
				}
				else
				{
					if (abs(r) < abs(p))
					{
						swap(heap[i*2+1], heap[i]);
					}
					else
					{
						if (abs(r) == abs(p))
						{
							if (r < p)
							{
								swap(heap[i*2+1], heap[i]);
							}
							else
							{
								break;
							}
						}
						else
						{
							break;
						}
					}
				}
			}
		}
	}


}
int main()
{
	cin >> N;
	while (N--)
	{
		int op;
		cin >> op;

		if (op == 0)
		{
			pop();
		}
		else
		{
			push(op);
		}
	}

	return 0;
}

djm03178 6년 전 1

pop을 할 때는 루트와 마지막 노드를 교환한 뒤에 그 노드가 제자리를 찾아갈 때까지 반복적으로 자식 노드와 교환을 해줘야 되는데, 이 코드에서는 pop에서 i가 절대 증가하지 않고 루트 자리만 지키고 있기 때문에 문제가 됩니다.

간단한 반례로, 1부터 10까지 push 하고 계속 팝해보면 틀리는 때가 나옵니다.

his130 6년 전 0

for문에서 증가값을 비워놓고, 까먹어버렸네요!! 감사합니다.

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

문제

문제

출처

ICPC

정말 긴 코드인데 봐주실 수 있나요?ㅠㅠ

his130 6년 전 0

djm03178 6년 전 1

his130 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말