BOJ_2696_중앙값구하기

걸린 시간: 20m

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

사고 과정:

BOJ 1655 가운데를 말해요와 로직이 동일합니다.

package BOJ_2696_중앙값구하기;
import java.util.*;

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

        while(T-- >0){

            int N = sc.nextInt();
            PriorityQueue<Integer> minHeap = new PriorityQueue<>();
            PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
            StringBuilder sb = new StringBuilder();
            int cnt = 0;

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

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

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

                    maxHeap.offer(min);
                    minHeap.offer(max);
                }
                if(i % 2 == 1){
                    cnt++;
                    sb.append(maxHeap.peek()).append(" ");

                }
            }
            System.out.println(cnt);
            System.out.println(sb);
        }
    }
}