[우선순위큐] 백준 1655번 : 가운데를 말해요 - C/C++

www.acmicpc.net/problem/1655

1655번: 가운데를 말해요

1. 문제

주어지는 값들 중에서 현재 중간값을 출력한다.

 

2. 해결

1) 최대힙(Max Heap)과 최소힙(Min Heap)을 구현해야 한다.

왜냐하면 최대힙은 root 보다 모두 작은 값들로 이루어져 있고, 최소힙은 root 보다 모두 큰 값들로 이루어져 있다.

따라서 최대힙 또는 최소힙의 root가 중간값이다.

     MaxHeap                   MinHeap

        Root                         Root

           |                              |

Root 보다 작은 수들     Root 보다 큰 수들

 

2) 최대힙과 최소힙에 순서대로 하나씩 입력값을 넣어주고 Heap을 구성한다.

만약 최대힙의 Root > 최소힙의 Root 이면, 각 값을 바꿔고 Heapify 한다.

(해당 문제에서 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 하기 때문)

 

※ 우선순위큐는 직접 구현하였습니다.

 

3. 구현

#include <stdio.h>

int N;
int minHeap[100001];
int maxHeap[100001];
int minHeapSize = 0;
int maxHeapSize = 0;

void minHeapPush(int value) {
	minHeap[minHeapSize] = value;
	int current = minHeapSize;
	while (current > 0 && minHeap[current] < minHeap[(current - 1) / 2]) {
		int temp = minHeap[(current - 1) / 2];
		minHeap[(current - 1) / 2] = minHeap[current];
		minHeap[current] = temp;
		current = (current - 1) / 2;
	}
	minHeapSize++;
}

void maxHeapPush(int value) {
	maxHeap[maxHeapSize] = value;
	int current = maxHeapSize;
	while (current > 0 && maxHeap[current] > maxHeap[(current - 1) / 2]) {
		int temp = maxHeap[(current - 1) / 2];
		maxHeap[(current - 1) / 2] = maxHeap[current];
		maxHeap[current] = temp;
		current = (current - 1) / 2;
	}
	maxHeapSize++;
}

void minHeapify() {
	int current = 0;
	while (current * 2 + 1 < minHeapSize)
	{
		int child;
		if (current * 2 + 2 == minHeapSize) child = current * 2 + 1;
		else child = minHeap[current * 2 + 1] < minHeap[current * 2 + 2] ? current * 2 + 1 : current * 2 + 2;
		
		if (minHeap[current] < minHeap[child]) break;
		
		int temp = minHeap[current];
		minHeap[current] = minHeap[child];
		minHeap[child] = temp;
		current = child;
	}
}

void maxHeapify() {
	int current = 0;
	while (current * 2 + 1 < maxHeapSize)
	{
		int child;
		if (current * 2 + 2 == maxHeapSize) child = current * 2 + 1;
		else child = maxHeap[current * 2 + 1] > maxHeap[current * 2 + 2] ? current * 2 + 1 : current * 2 + 2;

		if (maxHeap[current] > maxHeap[child]) break;

		int temp = maxHeap[current];
		maxHeap[current] = maxHeap[child];
		maxHeap[child] = temp;
		current = child;
	}
}

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

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

		if (maxHeapSize == minHeapSize) 
			maxHeapPush(value);
		else 
			minHeapPush(value);

		if (maxHeapSize > 0 && minHeapSize > 0 && maxHeap[0] > minHeap[0]) {
			int temp = maxHeap[0];
			maxHeap[0] = minHeap[0];
			minHeap[0] = temp;

			minHeapify();
			maxHeapify();
		}

		printf("%d\n", maxHeap[0]);
	}
}

 

geonhee7721/PS-Backjoon