가운데를 말해요

https://www.acmicpc.net/problem/1655
난이도는 Gold2
어려웠다. 처음에는 우선순위큐를 가운데값으로 만드는 걸 중복이 허용된 이분트리처럼 만들어 보려고 하였으나 실패
쉽게 구현할 좋은 방법을 찾게 되었다.
가운데를 기준으로 heap을 두개 만든다. 왼쪽 힙에는 내림차순의 우선순위큐로 오른쪽 힙에는 오른차순의 우선순위 큐
그 후 들어오는 값 마다 가운데 값과 비교하며 작을 경우 왼쪽큐에 클 경우 오른쪽 큐에 가운데 값일 경우 가운데 값과 교체하여 가운데 값을 옮겨 주었다.

순서도

import java.io.*;
import java.util.*;

public class Main {
    private static int N;

    public static void main(final String[] args) throws IOException {
        problem(new InputStreamReader(System.in));
    }

    public static void problem(final InputStreamReader isr) throws IOException {
        final BufferedReader br = new BufferedReader(isr);
        N = Integer.parseInt(br.readLine());
        final PriorityQueue<Integer> leftHeap = new PriorityQueue<>((o1,o2) -> o2 - o1);
        final PriorityQueue<Integer> rightHeap = new PriorityQueue<>((o1,o2) -> o1 - o2);
        int middle = Integer.parseInt(br.readLine());
        final StringBuilder st = new StringBuilder();
        st.append(middle + "\n");
        for(int i = 1 ; i < N ; i ++){
            final int num = Integer.parseInt(br.readLine());
            if (leftHeap.size() == rightHeap.size()){
                if (num > middle){
                    rightHeap.add(num);
                } else {
                    leftHeap.add(num);
                    final int leftPoll = leftHeap.peek();
                    if (leftPoll != middle){
                        rightHeap.add(middle);
                        middle = leftHeap.poll();
                    }
                }
                addString(st,i,middle);
                continue;
            }
            if (leftHeap.size() > rightHeap.size()) {
                if (num >= middle) {
                    rightHeap.add(num);
                } else  {
                    leftHeap.add(num);
                    rightHeap.add(middle);
                    middle = leftHeap.poll();
                }
                addString(st,i,middle);
                continue;
            }
            if (leftHeap.size() < rightHeap.size()){
                if (num > middle){
                    rightHeap.add(num);
                    leftHeap.add(middle);
                    middle = rightHeap.poll();
                } else {
                    leftHeap.add(num);
                }
                addString(st,i,middle);
            }
        }
        System.out.println(st);
    }

    private static void addString(final StringBuilder st, final int i, final int middle){
        if (i != N-1){
            st.append(middle + "\n");
            return;
        }
        st.append(middle);
    }
}