[백준 1655] 가운데를 말해요

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

1655번: 가운데를 말해요

#include <cstdio>
#include <queue>
int N;

using namespace std;

priority_queue<int> PQ_small; // 작은 수들의 집합
priority_queue<int, vector<int>, greater<int>> PQ_big;	// 큰 수들의 집합

void add_num(int n)
{
	if (PQ_small.empty() || PQ_small.top() > n) {	//작은 수 들의 집합 중 가장 큰 수가 항상 중앙값이라고 생각
		PQ_small.push(n);
		if (PQ_small.size() > PQ_big.size() + 1) {
			PQ_big.push(PQ_small.top());
			PQ_small.pop();
		}
	}
	else {
		PQ_big.push(n);
		if (PQ_big.size() > PQ_small.size()) {
			PQ_small.push(PQ_big.top());
			PQ_big.pop();
		}
	}
}

int get_median(void)
{
	return PQ_small.top();	// 짝수개여도 중간에 있는 두 수 중 어차피 작은 수를 말할 것이므로
}


int main()
{
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		int n = 0;
		scanf("%d", &n);
		add_num(n);
		printf("%d\n", get_median());
	}
	return 0;
}

이 문제는 "우선순위 큐"를 써서 (원리를 알고 나면) 쉽게풀 수 있다. 

 

원리 및 규칙은 다음과 같다. 

1. 항상 작은 수 그룹이 하나 더 많거나 같은 상황을 만든다. 

    => 전체 데이터 개수가 짝수일 때 : 중앙값은 "작은 수 그룹 중 가장 큰 값"과 "큰 수 그룹 중 가장 작은 값" 이다.

    => 전체 데이터 개수가 홀수일 때 : 중앙값은 "작은 수 그룹 중 가장 작은 값" 이다. 

2. 가장 처음 입력받는 숫자는 무조건 작은 수 그룹에 추가시킨다. 

3. 작은 수 그룹의 제일 큰 숫자를 항상 중앙값이라고 생각하고, 새롭게 입력받는 숫자와 비교한다. 

     => (작은 수 그룹의 제일 큰 숫자 > 새로 입력 받은 숫자) 이면 작은 수 그룹에 넣어준다. 

     => (작은 수 그룹의 제일 큰 숫자 < 새로 입력 받은 숫자) 이면 큰 수 그룹에 넣어준다.

 

이러한 규칙을 바탕으로 코드를 구현하기 위해, 작은 수 그룹과 큰 수 그룹의 자료구조를 선택해야 한다. 

작은 수 그룹의 우선순위 기준 : less (숫자가 클 수록 중앙값의 후보가 될 수 있기 때문)

큰 수 그룹의 우선순위 기준 : greater (숫자가 작을수록 중앙값의 후보가 될 수 있기 때문)