[BOJ] 1655. 가운데를 말해요

문제 원본 : https://www.acmicpc.net/problem/1655

1655번: 가운데를 말해요

import java.io.*;
import java.util.Collections;
import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        int a;
        PriorityQueue<Integer> minHeap = new PriorityQueue();
        PriorityQueue<Integer> maxHeap = new PriorityQueue(Collections.reverseOrder());
        StringBuilder builder = new StringBuilder();

        for (int i = 0; i < n; ++i) {
            a = Integer.parseInt(br.readLine());
            if (minHeap.size() == maxHeap.size()) {
                maxHeap.add(a);
            } else {
                minHeap.add(a);
            }

            if (!minHeap.isEmpty() && !maxHeap.isEmpty() && maxHeap.peek() > minHeap.peek()) {
                maxHeap.add(minHeap.poll());
                minHeap.add(maxHeap.poll());
            }

            builder.append(maxHeap.peek()).append("\n");
        }

        bw.write(builder.toString());

        bw.close();
        br.close();
    }
}

• 아이디어 참고
• 우선순위 큐를 활용한 문제
• Max Heap과 Min Heap을 활용해서 값을 넣을 때마다 중간값을 찾을 수 있다.
• 규칙은 2가지
• Max Heap의 크기는 Min Heap의 크기와 같거나 1 더 크다.
• Min Heap의 모든 원소는 Max Heap의 모든 원소보다 크거나 같다.
• 만약 첫 번째 규칙 때문에 Max Heap의 원소가 더 커지면 서로 top을 Swap 한다.
• 그럼 Max Heap의 top이 항상 중간값을 가지게 된다.