[백준] 1655번 : 가운데를 말해요

가운데를 말해요

---

해결 방법

숫자가 주어질 때 마다 숫자들의 중간 값을 구해야 한다.

처음에 접근을 PriorityQueue를 다시 구현해야 하나? 아니면 Comparator를 오버라이딩 해야되나? 고민했다.

그렇기엔 너무 복잡했다. 결국 다른 분들의 풀이를 보고 왼쪽은 maxHeap으로 오른쪽은 minHeap으로 구현해 중간 값을 구할 수 있다는 아이디어를 얻었다.

여기서 중요한 포인트는 maxHeap에서의 노드 값이 minHeap의 노드 값보다 작아야 한다는 점이다.

그리고 처음에 PriorityQueue에 넣을 때 maxHeap으로 넣는 것을 선택해 마지막에도 maxHeap에서 뽑아내 출력하면 된다.

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

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

            if(!maxHeap.isEmpty() && !minHeap.isEmpty()){
                if(maxHeap.peek() > minHeap.peek()){
                    int temp = maxHeap.remove();
                    maxHeap.add(minHeap.remove());
                    minHeap.add(temp);
                }
            }

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

        System.out.println(sb);
    }
}