백준 : 1655번, 가운데를 말해요

문제 주소 : www.acmicpc.net/problem/1655

정답 비율 : 32.163% (2021.02.24 11:40 기준)

1655번: 가운데를 말해요

 

문제 조건 :

입력 : 첫 줄에는 N이 주어지고 그 후 N개의 정수(num)가 주어집니다. (N : 1 ~ 100,000, num : -10,000 ~ 10,000)

출력 : 0 ~ n번째 데이터 사이의 중간 값을 출력하세요.

시간 : 0.1초

 

문제 풀이 :

가장 먼저 떠오르는 것은 데이터가 들어올 때마다 정렬을 하여 중간 값을 찾는 것입니다. 정렬 알고리즘의 시간 복잡도가 O(NlogN)이므로 최대 시간 복잡도는 O(100000log100000)이 되겠습니다. 따라서 해당 방법은 시간 초과됩니다.

 

아이디어는 다음과 같습니다.

 

힙을 이용하여 루트 노드 기준으로 루트 노드 포함 왼쪽은 항상 최소 힙을 구성하고 루트 노드 포함 오른쪽은 항상 최대 힙을 구성하면  루트 노드는 항상 중간 값을 가지게 됩니다. 단, 루트 노드의 왼쪽에 있는 노드의 수와 루트 노드의 오른쪽에 있는 노드의 수의 차는 <= |1| 일 때 성립합니다. 1 일 때 성립하는 이유는 문제에서 N이 짝수이면 더 작은 N을 중간 값으로 취급한다고 했기 때문입니다.

 

< 문제풀기 위한 tree 모습 >

이처럼 heap을 구축한다고 하면 시간 복잡도는 O(2log(N/2))가 됩니다. 

 

과정 : 

1. 첫 번째 데이터는 루트 노드에 저장합니다. (N > 0) 첫 번째 데이터가 없는 일은 없습니다.

2. 루트 노드 기준으로 데이터가 들어올 때마다 좌변 우변에 데이터를 하나씩 입력합니다. (좌우 변을 각각 다른 힙을 봤을 때 힙의 평형을 이루기 위하여, 한쪽 힙에 데이터가 더 많은 경우에는 루트 노드는 더 이상 중간 값의 역할을 수행할 수 없게 됩니다.)

3. 입력한 데이터가 들어가 쪽의 힙을 구축하고 다시 반대 변의 힙을 구축합니다. (ex. 데이터가 4번에 들어갔으면 우선 최소 힙을 구축합니다. 그리고 최대 힙을 다시 구축합니다.)

 

코드는 다음과 같습니다.

 

C99

#include<stdio.h>

#define MAXSIZE 50000

int top;
int MaxHeap[MAXSIZE];
int MinHeap[MAXSIZE];
int minindex;
int maxindex;

void max_insert(int data)
{
	if(maxindex < MAXSIZE)
	{
		int sun = maxindex;
		int parent = (sun - 1) / 2;
		
		while(sun != 0 && MaxHeap[parent] < data)
		{
			MaxHeap[sun] = MaxHeap[parent];
			sun = parent;
			parent = (sun - 1) / 2;
		}
		MaxHeap[sun] = data;
		maxindex++;
	}
}

void min_insert(int data)
{
	if(minindex < MAXSIZE)
	{
		int sun = minindex;
		int parent = (sun - 1) / 2;
		
		while(sun != 0 && MinHeap[parent] > data)
		{
			MinHeap[sun] = MinHeap[parent];
			sun = parent;
			parent = (sun - 1) / 2;
		}
		MinHeap[sun] = data;
		minindex++;
	}
}

void max_delete()
{
	if(maxindex > 0)
	{
		int data = MaxHeap[0];
		int parent = 0;
		int sun = 1;
	
		while(sun < maxindex)
		{
			if(sun + 1 < maxindex && MaxHeap[sun] < MaxHeap[sun + 1])
				sun++;
			
			if(data >= MaxHeap[sun])
				break;
			
			MaxHeap[parent] = MaxHeap[sun];
			
			parent = sun;
			sun = parent * 2 + 1;
		}
		MaxHeap[parent] = data;
	}
}

void min_delete()
{
	if(minindex > 0)
	{
		int data = MinHeap[0];
		int parent = 0;
		int sun = 1;
		
		while(sun < minindex)
		{
			if(sun + 1 < minindex && MinHeap[sun] > MinHeap[sun + 1])
				sun++;
			
			if(data <= MinHeap[sun])
				break;
			
			MinHeap[parent] = MinHeap[sun];
			
			parent = sun;
			sun = parent * 2 + 1;
		}
		MinHeap[parent] = data;
	}
}

int main()
{
	int N, i = -1;
	scanf("%d", &N);
	
	scanf("%d", &top);
	
	printf("%d\n", top);
	
	for(i = 1;i < N; i++)
	{
		int tmp;
		scanf("%d", &tmp);
		
		if(i % 2)
		{
			min_insert(tmp);
			
			if(top > MinHeap[0])
			{
				int t = top;
				top = MinHeap[0];
				MinHeap[0] = t;
				
				if(top < MaxHeap[0] && maxindex != 0)
				{
					t = top;
					top = MaxHeap[0];
					MaxHeap[0] = t;
					
					max_delete();
				}
			}
		}
		else
		{
			max_insert(tmp);
			
			if(top < MaxHeap[0])
			{
				int t = top;
				top = MaxHeap[0];
				MaxHeap[0] = t;
				
				if(top > MinHeap[0])
				{
					t = top;
					top = MinHeap[0];
					MinHeap[0] = t;
					
					min_delete();
				}
			}
		}
		
		printf("%d\n", top);
	}
}

 

- 루트 노드 기준으로 좌변과 우변을 서로 다른 힙을 구현하였습니다. 

 

끝~~