[C] 백준 - 11279번: 최대 힙

8월 29일(화) - 자료 구조 (11279번)

11279번: 최대 힙

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

최초 생각 정리

- 직전에 풀이했던 "1927번: 최소 힙" 문제와 사실상 동일하다

- 다만 최소 힙과 최대 힙의 차이가 있기때문에,

  이전 풀이의 push함수와 pop함수안에 있는 부등호들을 모두 반대로 수정하면 풀이가 진행될 것으로 예상

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이

(풀이참고 -> https://jicoding.tistory.com/99)

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

#include <stdio.h>

int heap[100001];
int hn = 0;

void swap(int i, int j)
{
	int tmp = heap[i];
	heap[i] = heap[j];
	heap[j] = tmp;
}

void push(int x)
{
	heap[++hn] = x;

	for (int i = hn; i > 1; i /= 2)
	{
		if (heap[i] > heap[i / 2])
		{
			swap(i, i / 2);
		}
		else
		{
			break;
		}
	}
}

int pop(void)
{
	int top = heap[1];
	heap[1] = heap[hn];
	heap[hn--] = 0;

	int i = 1;
	while (i * 2 <= hn)
	{
		// 자식이 1명일 경우
		if (heap[i * 2 + 1] == 0)
		{
			if (heap[i] > heap[i * 2])
			{
				break;
			}
			else if (heap[i] < heap[i * 2])
			{
				swap(i, i * 2);
				i = i * 2;
			}
			else
			{
				break;
			}
		}

		// 자식이 2명일 경우
		else
		{
			if (heap[i] > heap[i * 2] && heap[i] > heap[i * 2 + 1])
			{
				break;
			}
			else if (heap[i * 2] >= heap[i * 2 + 1])
			{
				swap(i, i * 2);
				i = i * 2;
			}
			else if (heap[i * 2] < heap[i * 2 + 1])
			{
				swap(i, i * 2 + 1);
				i = i * 2 + 1;
			}
			else
			{
				break;
			}
		}
	}

	return top;
}

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

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

		if (x == 0)
		{
			if (hn == 0)
			{
				printf("%d\n", 0);
			}
			else
			{
				printf("%d\n", pop());
			}
		}
		else
		{
			push(x);
		}
	}

	return 0;
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ