[백준] 2696 중앙값 구하기

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

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

int main()
{

	int iTestCase;
	cin >> iTestCase;
	while (iTestCase--)
	{
		int M;
		vector<int> iArr; //숫자 입력 받을 벡터 
		vector<int> iAns;
		cin >> M;
		for (int i = 0; i < M; i++)
		{
			int N;
			cin >> N;
			iArr.push_back(N);



			if (i == 0)
				iAns.push_back(iArr[i]);

			else if (i % 2 == 0)
			{
				sort(iArr.begin(), iArr.end()); 
				iAns.push_back(iArr[i / 2]);
                //홀수 번째 숫자가 입력될때 숫자벡터를 초기화 시키고 
                그 중앙값을 정답벡터에 넣어줌
                
			}
		}

		cout << (M + 1) / 2 << '\n';
		for (int i = 0; i < iAns.size(); i++)
		{
			cout << iAns[i] << " ";
		}
		cout << '\n';
	}

}

sort 함수를 여러번 사용하면 시간제한에 자주 걸리던데 다행이 안걸렸다.
알고리즘 분류를 보니 queue를 사용하는 문제였는데

우선순위큐 priority_queue를 사용해서 하나는 오름차순 하나는 내림차순으로 구현하고

priority_queue<int> maxHeap;
priority_queue<int, vector<int>, greater<int> > minHeap;

값을 한번씩 push 해주고
minHeap.top() < maxHeap.top()이므로 top() 값을 swap해준다.

minHeap은 greater(내림차순)으로 정렬되기 때문에 내부에서 또 swap이 일어나기를 반복하면서 maxHeap에 중앙값들만 모이게 되어 답이된다.