BOJ_1655_가운데를말해요

걸린 시간: 알고리즘 참고

알고리즘 분류: Heap, PriorityQueue, Median of a Stream

사고 과정

실시간으로 들어오는 값에 대한 중간값 처리가 필요했지만 값을 넣을때마다 정렬해주는 로직은 상당한 시간복잡도가 발생하기때문에 Priority Queue를 사용해야만 합니다.
중간값을 처리하는 로직 중 minHeap과 maxHeap을 동시에 할당하여 실시간으로
반영할 수 있는 로직이 있어 사용해봤습니다.

• maxHeap, minHeap 할당
• 각 Heap 사이즈 크기 비교
  크기가 같다면, maxHeap.offer
  다르다면 minHeap.offer
• maxHeap의 최댓값과 minHeap의 최솟값을 비교하여 maxHeap의 최댓값이 크면
  SWAP

package BOJ_1655_가운데를말해요;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < N; i++) {
            int num = sc.nextInt();

            if (maxHeap.size() == minHeap.size()) {
                maxHeap.offer(num);
            } else {
                minHeap.offer(num);
            }

            if (!minHeap.isEmpty() && maxHeap.peek() > minHeap.peek()) {
                int maxTop = maxHeap.poll();
                int minTop = minHeap.poll();

                maxHeap.offer(minTop);
                minHeap.offer(maxTop);
            }

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