BOJ 2696 - 중앙값 구하기

문제 링크

---

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

문제 해결

---

 1. 중앙 값을 구하기 위해서 우선 순위 큐(Priority Queue) 2개를 사용한다.

 2. 중앙 값을 변수 val에 저장한다. 그리고 val과 새로 주어진 값의 크기를 비교한다. 

주의할 점 || 생각해볼 점

---

 -

참고

---

 - 

	/*
	explanation in vjerksen.tistory.com
	*/
	#include<cstdio>
	#include<iostream>
	#include<string>
	#include<algorithm>
	#include<cstring>
	#include<set>
	#include<stack>
	#include<map>
	#include<cmath>
	#include<queue>
	#include<cstdlib>
	#include<vector>
	using namespace std;
	int T,N;
	int main(){
	cin >> T;
	while(T--){
	vector<int> ans;
	priority_queue<int> max_q,min_q;
	scanf("%d",&N);
	int temp,val;
	for(int i=1;i<=N;i++){
	scanf("%d",&temp);
	if(i==1){
	ans.push_back(temp);
	val=temp;
	continue;
	}
	if(val<temp){
	if(max_q.size()<=min_q.size()){
	max_q.push(-temp);
	}
	else{
	min_q.push(val);
	if(-max_q.top()>temp){
	val = temp;
	}
	else{
	val = -max_q.top();
	max_q.pop();
	max_q.push(-temp);
	}
	}
	}
	else{
	if(max_q.size()>=min_q.size()){
	min_q.push(temp);
	}
	else{
	max_q.push(-val);
	if(min_q.top()<temp){
	val = temp;
	}
	else{
	val = min_q.top();
	min_q.pop();
	min_q.push(temp);
	}
	}
	}
	if(i%2==1){
	ans.push_back(val);
	}
	}
	int cnt =0;
	printf("%d\n",N/2+1);
	for(int i=0;i<ans.size();i++){
	cnt++;
	printf("%d ",ans[i]);
	if(cnt==10){
	cnt=0;
	printf("\n");
	}
	}
	printf("\n");
	}
	}

view raw BOJ 2696.cpp hosted with ❤ by GitHub

※ 정확하고 부드러운 태클은 언제나 환영입니다.