백준 1655 가운데를 말해요 Java [우선순위 큐]

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

1655번: 가운데를 말해요

 

가운데 값을 기준으로 왼쪽에 최대 힙, 오른쪽에 최소 힙을 만들어주고

두 힙의 사이즈가 같거나 왼쪽이 1 더 크게 만들어서 왼쪽의 peek 값을 출력값에 넣어준다

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int N = Integer.parseInt(br.readLine());
        PriorityQueue<Integer> left = new PriorityQueue<>(Comparator.reverseOrder());
        PriorityQueue<Integer> right = new PriorityQueue<>();

        int Z = Integer.parseInt(br.readLine());
        left.add(Z);
        sb.append(Z).append("\n");
        for (int n = 1; n < N; n++) {
            Z = Integer.parseInt(br.readLine());
            if (left.peek() > Z) {
                left.add(Z);
                if (left.size() > right.size() + 1) {
                    right.add(left.poll());
                }
            } else {
                right.add(Z);
                if (right.size() > left.size()) {
                    left.add(right.poll());
                }
            }
            sb.append(left.peek()).append("\n");
        }
        sb.setLength(sb.length() - 1);
        System.out.println(sb);
    }
}