중앙값

문제

정수가 N개 주어진다. 홀수번째 수가 주어질 때마다, 지금까지 주어진 수의 중앙값을 구하는 프로그램을 작성하여라.

예를 들어 1, 4, 5, 3, 6가 주어진다면, 첫번째 수인 1을 입력받을 때 중앙값이 1이고, 세 번째 수인 5를 입력받을 때까지의 중앙값이 4이고, 다섯번째 수인 6을 입력받을 때까지의 중앙값이 4이므로 1, 4, 4를 순서대로 출력하는 것이다.

---

입력

첫 번째 줄에 주어지는 정수의 개수 N이 주어진다. (1 ≤ N ≤ 99,999, N은 홀수)

두 번째 줄부터 N개의 줄에 걸쳐 각 줄에 하나씩 정수가 주어진다. (1 ≤ 주어지는 정수 ≤ 1,000,000,000)

---

출력

홀수번째 수를 입력받을 때마다 그 때까지 입력받은 정수들의 중앙값을 한 줄에 하나씩 출력한다.

---

힌트

입력 예제

7

1 

9 

5 

3 

2 

8

8

출력 예제

1

5

3

5

#include <iostream> #include <fstream> #include <string.h> #include <algorithm> #include <set> #include <queue> //CenterValue --------------------- void CenterValue(); //CenterValue --------------------- int main(int argc, char** argv) { CenterValue(); return 0; } int N; struct comparator { bool operator () (int a, int b){ return a > b; } }; void CenterValue(){ //LEFT QUEUE------CenterValue------RIGHTQUEUE std::priority_queue<int,std::vector<int>,comparator> rightQ; std::priority_queue<int> leftQ ; std::cin >> N; int V1, V2; int x = 0; //중심추 int centerValue; std::cin>>centerValue; //값을 입력받고 std::cout<< centerValue << std::endl; for(int i=0; i<N/2; i++){ std::cin>>V1 >> V2; //값을 2개 입력 받음 x = 0; //기준을 잡는다. if(V1 > centerValue){ x++; rightQ.push(V1); }else{ x--; leftQ.push(V1); } if(V2 > centerValue){ rightQ.push(V2); x++; }else{ x--; leftQ.push(V2); } if(x==0){ //기준이 안바뀜 }else if(x>0){ //무게중심을 맞춰줌 leftQ.push(centerValue); centerValue = rightQ.top(); rightQ.pop(); }else{ rightQ.push(centerValue); centerValue = leftQ.top(); leftQ.pop(); } std::cout<< centerValue << std::endl; } }