문제

어떤 수열을 읽고, 홀수번째 수를 읽을 때 마다, 지금까지 입력받은 값의 중앙값을 출력하는 프로그램을 작성하시오.

예를 들어, 수열이 1,5,4,3,2 이면, 홀수번째 수는 1번째 수, 3번째 수, 5번째 수이고, 1번째 수를 읽었을 때 중앙값은 1, 3번째 수를 읽었을 때는 4, 5번째 수를 읽었을 때는 3이다.

문제풀이

사용한 알고리즘 : priority_queue

중앙값을 기준으로 중앙값보다 작은 값들을 저장할 priority_queue (: 큰 값이 위로),

큰 값들을 저장할 priority_queue ( : 작은 값이 위로 )를 만들어줍니다.

첫 입력으로 들어오는 값을 중앙값으로 잡고, 다음 입력부터 중앙값보다 큰지 작은지를 판단하여 과정(1)에서 만들어 놓은 두 priority_queue에 저장해줍니다.

홀수번째 입력마다 중앙값을 알맞게 맞춰줘야 합니다.

즉, 중앙값 기준, 작은 값들을 저장한 pq와 큰 값들을 저장한 pq의 사이즈가 같아야 합니다.

한쪽 pq가 더 크다면, 두 pq의 사이즈가 같아질 때까지 중앙값을 사이즈가 작은 쪽에 넣어주고, 사이즈가 큰 쪽에서 값을 하나 빼서 해당 값을 중앙값으로 생각해줍니다.

한 줄에 10개까지만 출력해주어야합니다.

	#include<bits/stdc++.h>
	using namespace std;

	int T, N;
	int mid;

	int main() {ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> T;
	while (T--) {
	vector<int> ans;
	priority_queue<int, vector<int>, less<int>> mini; // 큰게 위로
	priority_queue<int, vector<int>, greater<int>> maxi; // 작은게 위로

	cin >> N;
	for (int i = 1; i <= N; ++i) {
	int num;
	cin >> num;

	if (i == 1) mid = num;
	else {
	if (mid > num) mini.push(num);
	else maxi.push(num);
	}

	if (i % 2 == 1) {// 홀수 일 때는 mini 와 maxi 의 크기가 같아야 한다.
	while (mini.size() > maxi.size()) {
	maxi.push(mid);
	mid = mini.top();
	mini.pop();
	}
	while (mini.size() < maxi.size()) {
	mini.push(mid);
	mid = maxi.top();
	maxi.pop();
	}
	ans.push_back(mid);
	}
	}
	cout << ans.size() << '\n';
	for (int i = 0; i < ans.size(); ++i) {
	if (i != 0 && i % 10 == 0) cout << '\n';
	cout << ans[i] << ' ';
	}
	cout << '\n';

	}

	return 0;
	}

view raw BOJ 2696.cpp hosted with ❤ by GitHub