백준 2696번 : 중앙값 구하기 Java

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

2696번: 중앙값 구하기

중앙값을 다이렉트하게 뽑아낼 수 있는 자료구조 라이브러리는 존재하지 않는다.

 

하지만 우선순위 큐 두개를 이용해서 중앙값을 적은 cost로 뽑아 낼 수 있다.

 

import java.util.*;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) throws IOException {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int t = Integer.parseInt(br.readLine());

        for(int T=0; T<t; T++){
            maxHeap.clear();
            minHeap.clear();
            int n = Integer.parseInt(br.readLine());
            bw.write((n/2 + 1) + "\n");
            int lines = n%10==0 ? n/10 : n/10 + 1;
            int cnt = 0;
            int printed = 0;
            for(int i=0; i<lines; i++){
                String[] split = br.readLine().split(" ");

                for(int j=0; j<split.length;j++){
                    int cur = Integer.parseInt(split[j]);
                    if(cnt==0){
                        minHeap.add(cur);
                    }
                    else{
                        if(cur<=minHeap.peek()){
                            maxHeap.add(cur);
                        }
                        else {
                            minHeap.add(cur);
                        }
                    }
                    cnt++;


                    if(cnt%2==1){
                        while(maxHeap.size() >= minHeap.size()){
                            minHeap.add(maxHeap.peek());
                            maxHeap.poll();
                        }

                        while(maxHeap.size() + 1 < minHeap.size()){
                            maxHeap.add(minHeap.peek());
                            minHeap.poll();
                        }
                        bw.write(minHeap.peek().toString() + " ");

                        printed++;

                        if(printed%10==0) bw.write("\n");
                    }

                }
            }
            bw.write("\n");
        }
        bw.flush();
    }
}