[백준 2696] 중앙값 구하기 (C++)

문제 링크: https://www.acmicpc.net/problem/2696

2696번: 중앙값 구하기

1. 주의할 점

- 홀수번째마다 정렬해서 중앙값을 구하지 않는다

 

2. 구현

- 2가지의 우선순위 큐를 사용한다(오름차순 정렬, 내림차순 정렬 각각 1개씩)

- 중앙값을 기준으로 왼쪽에는 내림차순으로 정렬된 Left 우선순위큐를, 오른쪽에는 오름차순으로 정렬된 Right 우선순위큐가 있다고 가정한다

- 홀수번째마다 Right와 Left의 크기를 비교하며 만약 한쪽으로 치우쳐진 경우, 옆으로 1개씩 밀어낸다(아래 TC를 통해 원리를 이해하자)

TC #1

1

3

1 7 10

i=0)

Median: 1, Left: Empty, Right: Empty

i=1)

Median: 1, Left: Empty, Right: 7

i=2)

Median: 1, Left: Empty, Right: 7 10

 

위의 경우, i=2일때 치우쳐져있으므로 Median을 Left로, Right의 Top을 Median으로 민다

이후 상태

Median: 7, Left: 1, Right: 10

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

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int test, num, val, median;
	cin >> test;
	for (int t = 0; t < test; t++) {
		priority_queue<long long, vector<long long>, less<long long>> left;		//중앙값>= 를 만족하는 수
		priority_queue<long long, vector<long long>, greater<long long>> right;			//중앙값<= 를 만족하는 수
		vector<int> v;
		cin >> num;
		for (int i = 0; i < num; i++) {
			cin >> val;
			if (i == 0) median = val;
			else {
				if (val <= median) left.push(val);
				else right.push(val);

			}
			if (i % 2 == 0) {
				if (left.size() > right.size()) {
					right.push(median);
					median = left.top();
					left.pop();
				}
				else if (left.size() < right.size()) {
					left.push(median);
					median = right.top();
					right.pop();
				}
				v.push_back(median);
			}
		}
		cout << num / 2 + 1 << '\n';
		for (int i = 0; i < v.size(); i++) {
			cout << v[i] << " ";
			if ((i+1) % 10 == 0) cout << '\n';
		}
		cout << '\n';
	}
	return 0;
}