[BOJ 1655] 가운데를 말해요

한동안 SWEA와 연구실 인턴을 병행하다보니 백준을 풀 시간이 거의 없었다. SWEA는 되도록 유출이 되지 않도록 올리지 않기 때문에 백준 문제를 풀고 후기를 쓴다.

 

https://www.acmicpc.net/problem/1655

1655번: 가운데를 말해요

A. 사용한 알고리즘이나 자료구조

먼저 heap을 사용하였다. min heap과 max heap 둘다 사용해주었다. 여기서 가운데를 찾아야 하기때문에 첫번째 원소를 max heap에 저장을 해준다. 핵심 개념은 maxheap[0]과 minheap[0]에 중간 값들을 저장할 것이다. 홀수개의 경우 maxheap의 원소 개수가 더 많도록 코드를 짠다. 그렇기 때문에 첫번째 원소를 max heap에 push해주고 그 다음부터 들어오는 원소가 max heap의 root 원소보다 클 경우 min heap에 push하고 작을경우 max heap에 push 해준다. 그리고 max heap의 원소 개수가 min heap의 원소 개수보다 2이상 클경우 root를 pop한다음 min heap에 push해준다. 만약 min heap의 원소 개수가 max heap의 원소 개수 보다 많을 경우 pop하여 max heap에 넣어준다. 이렇게 진행해준다면 홀수개가 들어왔을때 min heap 에는 max heap의 root원소보다 큰 것들만 존재하고 max heap에선 root보다 다 작은 것들이 존재하기 때문에 max heap의 root가 중간 값이 된다. 만약 짝수개가 들어왔을 경우 max heap의 root와 min heap의 root중 더 작은 것을 출력하면 된다. 하지만 max heap의 root가 언제나 작기 때문에 max heap 의 root를 출력한다.

 

B.코드

#include<iostream>

using namespace std;
int n;
int mincnt=0;
int maxcnt=0;
int minheap[500001];
int maxheap[500001];


void max_push(int num)
{
	maxheap[maxcnt++] = num;

	int cur = maxcnt - 1;

	while (cur > 0 && maxheap[cur] > maxheap[(cur - 1) / 2])
	{
		int temp = maxheap[cur];
		maxheap[cur] = maxheap[(cur-1)/2];
		maxheap[(cur - 1) / 2] = temp;
		cur = (cur - 1) / 2;
	}
}

void min_push(int num)
{
	minheap[mincnt++] = num;
	int cur = mincnt - 1;

	while (cur > 0 && minheap[cur] < minheap[(cur - 1) / 2])
	{
		int temp = minheap[cur];
		minheap[cur] = minheap[(cur - 1) / 2];
		minheap[(cur - 1) / 2] = temp;
		cur = (cur - 1) / 2;
	}
}

int max_pop()
{
	int ret = maxheap[0];
	maxheap[0] = maxheap[--maxcnt];

	int cur = 0;
	while (cur*2+1<maxcnt)
	{
		int child;
		
		if (cur * 2 + 2 == maxcnt)
			child = cur * 2 + 1;
		else
			child = maxheap[cur * 2 + 1] > maxheap[cur * 2 + 2] ? cur * 2 + 1 : cur * 2 + 2;
		
		if (maxheap[cur] > maxheap[child])
			break;

		int temp = maxheap[cur];
		maxheap[cur] = maxheap[child];
		maxheap[child] = temp;
		cur = child;
	}

	return ret;
}

int min_pop()
{
	int ret = minheap[0];
	minheap[0] = minheap[--mincnt];

	int cur = 0;
	while (cur * 2 + 1 < mincnt)
	{
		int child;

		if (cur * 2 + 2 == mincnt)
			child = cur * 2 + 1;
		else
			child = minheap[cur * 2 + 1] < minheap[cur * 2 + 2] ? cur * 2 + 1 : cur * 2 + 2;

		if (minheap[cur] < minheap[child])
			break;

		int temp = minheap[cur];
		minheap[cur] = minheap[child];
		minheap[child] = temp;
		cur = child;
	}

	return ret;
}
int main(int argc, char** argv)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;
	int temp;
	n--;
	cin >> temp;
	max_push(temp);
	cout << maxheap[0]<<"\n";
	while (n--)
	{
		cin >> temp;
		if (temp > maxheap[0])
			min_push(temp);
		else
			max_push(temp);

		if (mincnt > maxcnt)
			max_push(min_pop());
		else if (maxcnt > mincnt + 1)
			min_push(max_pop());
		
		cout << maxheap[0] << "\n";
	}
	return 0;
}

C. 후기

library를 사용하지 않았기 때문에 하나부터 열까지 다 코드를 짰다. 시간은 더 걸리지만 그래도 개념을 제대로 잡고 가는것 같아 뿌듯하다.