문제
정수가 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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 | #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; }} |