우선순위 큐 - 백준 1655번 가운데를 말해요 ✨(running median heap)

배워갈 게 많은 문제라고 생각해서 특별히 별표 표시해둠

www.acmicpc.net/problem/1655

1655번: 가운데를 말해요

IDEA

맨 처음에는 단순히 ? 정렬한 후에 중앙값을 인덱스로 하는 배열값을 선택하면 되지 않나 라고 생각했는데 

기본 sort를 사용하면 시간복잡도가 $nlog{n}$으로 시간제한 0.1초를 절대 넘기지 못할 거 같았다. 

그래서 고민고민 해보다 다른 사람들의 블로그를 참고해서 풀었다.

엄청 신기했는데 running median algorithm이라고 유명한 알고리즘이라고 한다. 

입력을 받을때마다 중앙값을 구하는 문제로, 매번 중앙값이 바뀌기에 running median인 거 같다. 

 

핵심 아이디어를 말하기 전에 중앙값에 대해서 생각을 해보자. 편의상 홀수개로 씀.

통계적으로 바라봤을 때 중앙값을 구하려면 정렬을 먼저해야한다. 

1  2  4  9  5  5  5 >> 1  2  4  5  5  5  9

중앙값은 5가 된다. 그러면 중앙값을 기준으로 앞의 숫자 3개와 뒤의 숫자 3개를 비교해보자. 

앞의 숫자 3개는 중앙값보다 작거나 같다. 그러면 중앙값 기준 이전 숫자들은 이후 숫자들보다 같거나 작아야한다. 

뒤의 숫자 3개 또한 중앙값보다 크거나 같다. 그러면 중앙값 기준 이후 숫자들은 이전 숫자들보다 같거나 커야한다. 

 

핵심아이디어는 최대힙 + 최소힙 , 힙 2개를 사용하는거다. 

즉 중앙값 이전은 최대힙 , 중앙값 이후는 최소힙을 사용한다고 생각하면 된다. 

최대힙에서의 top 과 최소힙에서의 top 중 하나가 중앙값이 된다. 

 

1. 맨 처음 값은 max_heap에 넣어준 후 중앙값 = 처음값으로 업데이트해준다. 

med  = 1 (굵은 글씨 = 중앙값)

 

2. 중앙값과 비교 후 중앙값보다 크다면 min heap으로 작다면 max heap으로 보낸다. 

힙들의 크기는 서로 같거나 1만큼만 커야한다. 

3. max heap과 min heap의 사이즈를 비교해보자. 

만일 한 쪽이 나머지 한 쪽에 비해 사이즈가 1보다 크다면 (2 이상) 사이즈가 더 큰 쪽의 top 원소를 더 작은 쪽으로 옮겨준다. 

 

4.  3을 거치면 두개 힙의 사이즈가 같거나 1만큼 차이가 난다.  

4 - 1. max_heap과 min_heap의 사이즈가 같다면 max heap의 top 이 중앙값이 된다. (이건 문제조건에 따라 달라지는데, 지금 문제에서는 짝수개면 더 작은 값이 중앙값이라고 써져있음)

4 - 2. 사이즈가 다르다면 사이즈가 더 큰 쪽의 top이 중앙값이 된다. 

 

예를 들어 설명해보자. 

case 1) mid = 1

MAX	1
MIN

case 2 -> 4-1) mid = 1 보다 크므로 min heap에 삽입 

MAX	1
MIN	5

case 2 -> 4-2)  mid = 1보다 크므로 min heap에 삽입 이후 minheap의 사이즈가 더 크므로 top이 mid로 업데이트

MAX	1
MIN	2	5

case 2 )  mid = 2보다 크므로 min heap에 삽입 

MAX	1
MIN	2	5	10

case 2-> 3 -> 4-1) min heap 이 max heap보다 2만큼 크므로 min heap의 top인 2를 max heap으로 넘겨준다.

MAX	2	1
MIN	5	10

case 2 -> 4-2)  mid = 2보다 작으므로 max heap에 삽입 이후 maxheap의 사이즈가 더 크므로 top이 mid로 업데이트

MAX	2	1	-99
MIN	5	10

case 2 -> 4-1)  mid = 2보다 크므로 min heap에 삽입 이후 사이즈가 같으므로 maxheap의 top이 mid

MAX	2	1	-99
MIN	5	7	10

case 2 -> 4-2 ) mid = 2 보다 크므로 min heap에 삽입 후 min heap의 사이즈가 더 크므로 top 이 mid

MAX	2	1	-99
MIN	5	5	7	10

 

CODE

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;

priority_queue<int, vector<int>, less<int>> max_heap;
priority_queue<int, vector<int>, greater<int>> min_heap;

int main() {
	int n, num, med;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &num);
		if (i == 0) {
			max_heap.push(num);
			med = num;
			printf("%d\n", max_heap.top());
			continue;
		}
		//중앙값과 비교 후 힙에 삽입
		if (med <= num) min_heap.push(num);
		else max_heap.push(num);

		// 이후 size의 차이가 크지 않은지 비교 -> 크다면 넘겨줌
		if (max_heap.size() > min_heap.size() + 1) {
			int topnum = max_heap.top();
			max_heap.pop();
			min_heap.push(topnum);
		}

		else if (min_heap.size() >= max_heap.size() + 1) {
			int topnum = min_heap.top();
			min_heap.pop();
			max_heap.push(topnum);
		}


		//이후 중앙값 출력 -> 사이즈가 같다면 max의 top , 사이즈가 다르면 큰 쪽 top
		if (max_heap.size() >= min_heap.size()) {
			printf("%d\n", max_heap.top());
			med = max_heap.top();
		}

		else {
			printf("%d\n", min_heap.top());
			med = min_heap.top();
			}
		}
	}