# [Gold II] 중앙값 구하기 #### [문제 링크](https://www.acmicpc.net/problem/2696) ## 문제 설명 <p>어떤 수열을 읽고, 홀수번째 수를 읽을 때 마다, 지금까지 입력받은 값의 중앙값을 출력하는 프로그램을 작성하시오.</p> <p>예를 들어, 수열이 1, 5, 4, 3, 2 이면, 홀수번째 수는 1번째 수, 3번째 수, 5번째 수이고, 1번째 수를 읽었을 때 중앙값은 1, 3번째 수를 읽었을 때는 4, 5번째 수를 읽었을 때는 3이다.</p> ## 입력 <p>첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 각 테스트 케이스의 첫째 줄에는 수열의 크기 M(1 ≤ M ≤ 9999, M은 홀수)이 주어지고, 그 다음 줄부터 이 수열의 원소가 차례대로 주어진다. 원소는 한 줄에 10개씩 나누어져있고, 32비트 부호있는 정수이다.</p> ## 출력 <p>각 테스트 케이스에 대해 첫째 줄에 출력하는 중앙값의 개수를 출력하고, 둘째 줄에는 홀수 번째 수를 읽을 때 마다 구한 중앙값을 차례대로 공백으로 구분하여 출력한다. 이때, 한 줄에 10개씩 출력해야 한다.</p> ## 풀이 #### maxHeap과 minHeap을 가진 두개의 우선순위큐를 가지고, maxHeap에는 작은 i+1개의 원소, minHeap에는 큰 i개의 원소를 넣고 중앙값을 찾으면 된다. ``` c++ #include<bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while(t--) { int n; cin >> n; priority_queue<int> min; // 작은 i+1개 (제일 큰게 top) priority_queue<int, vector<int>, greater<int>> max; // 큰 i개 (제일 작은게 top) cout << (n+1)/2; for(int i=0;i<n;i++) { int input; cin >> input; min.push(input); if(max.size()) { int top = max.top(); max.pop(); min.push(top); } if((min.size()+max.size())%2==1) { while(min.size()!=max.size()+1) { int top = min.top(); min.pop(); max.push(top); } if(i/2%10==0) cout << '\n'; cout << min.top() << ' '; } } cout << '\n'; } } ```