[C/C++] 백준 1655번

문제출처: https://www.acmicpc.net/problem/1655

1655번: 가운데를 말해요

[ 문제 ]

백준이는 동생에게 "가운데를 말해요" 게임을 가르쳐주고 있다. 백준이가 정수를 하나씩 외칠때마다 동생은 지금까지 백준이가 말한 수 중에서 중간값을 말해야 한다. 만약, 그동안 백준이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다.

예를 들어 백준이가 동생에게 1, 5, 2, 10, -99, 7, 5를 순서대로 외쳤다고 하면, 동생은 1, 1, 2, 2, 2, 2, 5를 차례대로 말해야 한다. 백준이가 외치는 수가 주어졌을 때, 동생이 말해야 하는 수를 구하는 프로그램을 작성하시오

[ 입력 ]

첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -10,000보다 크거나 같고, 10,000보다 작거나 같다.

[ 출력 ]

한 줄에 하나씩 N줄에 걸쳐 백준이의 동생이 말해야 하는 수를 순서대로 출력한다.

[ 풀이 ]

우선순위 큐로는 최대 힙(Max heap)이나 최소 힙(Min heap)만을 구현할 수 있기에 중간값을 어떻게 출력할 수 있을지 상당히 오래 고민했다. 결국 혼자서 해결하지 못해 다른 분들의 풀이를 참고했고, 그 중에서도 https://www.crocus.co.kr/625 님의 "중간값 구하기 알고리즘" 부분만 읽어보고 소스코드는 스스로 구현해 보았다.

 

다음은 문제를 해결하기 위한 기본 가정이다.

(1) 최대 힙과 최소 힙을 각각 하나씩 사용한다.

(2) 최대 힙의 size는 최소 힙의 size와 같거나 '반드시' 1만 크다.

(3) 최대 힙의 top 원소 <= 최소 힙의 top 원소

(4) 만약 (3)을 만족하지 않는다면 최대 힙의 top원소와 최소 힙의 top원소를 swap한다.

 

이 가정들을 유지하면서 두 개의 우선순위 큐에 원소를 넣고, 최대 힙의 top원소를 pop한다면 외친 수의 개수가 짝수개인 경우 중간에 있는 두 수 중에서 작은 수를 출력할 수 있고, 홀수개인 경우 중간값을 출력할 수 있다.

 

[1] 짝수개일 경우 - 최대 힙과 최소 힙의 원소들을 펼쳐서 나열했다고 가정했을 때

최대 힙이므로 max의 왼쪽 원소는 max보다 항상 작은 값 <  최대 힙의 max < 최소 힙의 min < 최소 힙이므로 min보다 큰 값들

 

가정(2)로 인해 짝수개일 때는 최대 힙과 최소 힙의 size가 같으므로 최대 힙의 max 출력 시 중간에 있는 두 수 중에서 작은 수 출력이 가능하다.

 

 

[2] 홀수개일 경우 - 최대 힙과 최소 힙의 원소들을 펼쳐서 나열했다고 가정했을 때

가정(2)로 인해 홀수개일 때는 최대 힙의 size가 최소 힙의 size보다 1크다. 그러므로 최대 힙의 max출력 시 정확한 중간값 출력이 가능하다.

 

※주의할 점: 반드시 가정 (4) "만약 최대 힙의 top 원소 <= 최소 힙의 top 원소을 만족하지 않는다면 최대 힙의 top원소와 최소 힙의 top원소를 swap한다."을 지켜야만 정확한 중간값을 출력할 수 있다.

 

#include <iostream>
#include <queue>
#include <functional>

using namespace std;

int main(void)
{
	priority_queue<int> max_pq;
	priority_queue<int, vector<int>, greater<int>> min_pq;
	
	int n, x;
	scanf("%d", &n);
	
	for ( int i = 0 ; i < n ; i++ )
	{
		scanf("%d", &x);
		if ( max_pq.size() == min_pq.size() )
		{
			max_pq.push(x);
		}
		else
		{
			min_pq.push(x);
		}
		
		if ( min_pq.size() == 0 )
		{
			printf("%d\n", max_pq.top());
			continue;
		}
		
		if ( max_pq.top() > min_pq.top() )
		{
			int temp1 = max_pq.top();
			int temp2 = min_pq.top();
			max_pq.pop();
			min_pq.pop();
			max_pq.push(temp2);
			min_pq.push(temp1);
		}
		
		printf("%d\n", max_pq.top());
	}
	
	return 0;
}