백준 2696 : 중앙값 구하기

저세상 개발자 2021. 7. 3. 20:07

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

2696번: 중앙값 구하기

첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 각 테스트 케이스의 첫째 줄에는 수열의 크기 M(1 ≤ M ≤ 9999, M은 홀수)이 주어지고, 그 다음 줄부터 이 수열의 원소가 차례대로 주

www.acmicpc.net

어떤 배열이 주어졌을 때 중앙값을 찾는 문제이다. 직전에 포스팅했던 K번째 수 찾기와 동일한 로직으로 풀 수 있다.

K번 째 수 찾기 - https://unfunhy.tistory.com/43

[python] K번 째 수 찾기

import heapq def findKth(myInput, k) : ''' 매 순간마다 k번째로 작은 원소를 리스트로 반환합니다. ''' result = [] l = [] #max_heap r = [] #min_heap for i in myInput: # max_heap이 비어있거나, max_heap..

unfunhy.tistory.com

#include <iostream>
#include <queue>
#include <vector>

#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;

int main() {
	fastio;

	int t, m, n;
	cin >> t;
	while (t--) {
		cin >> m;

		priority_queue<int> l; // max_heap
		priority_queue<int> r; // min_heap
		vector<int> ans;

		for (int i = 1; i <= m; i++) {
			cin >> n;
			if (l.empty() || l.top() >= n) l.emplace(n);
			else r.emplace(-n);

			if (l.size() > r.size() + 1) {
				r.emplace(-l.top());
				l.pop();
			}
			else if (l.size() < r.size()) {
				l.emplace(-r.top());
				r.pop();
			}

			if (i & 1) ans.push_back(l.top());
		}
		cout << ans.size() << '\n';
		for(int i : ans) cout << i << ' ';
		cout << '\n';
	}
	return 0;
}

위는 c++ 구현 코드이다. 파이썬에서 heapq는 min heap인 반면 c++에서 pq는 max heap임을 참고바란다.

메모리: 2156 kb

시간: 0 ms