[우선순위 큐] 중간 값 구하기(백준 2696번, 자바)☆

2696번: 중앙값 구하기 (acmicpc.net)

2696번: 중앙값 구하기

 

 

 

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

public class Main {

	static PriorityQueue<Integer> max_heap;
	static PriorityQueue<Integer> min_heap;
	static int median;
	
	public static void main(String[] args) throws Exception{
		
		Scanner sc=new Scanner(System.in);
		int T=sc.nextInt();
	
		
		for(int t_c=1;t_c<=T;t_c++) {
			
			int M=sc.nextInt();
			
			min_heap=new PriorityQueue<>();
			max_heap=new PriorityQueue<>(new Comparator<Integer>() {

				@Override
				public int compare(Integer o1, Integer o2) {
					// TODO Auto-generated method stub
					return o2-o1;
				}
				
				
			});
			int n;
			
			System.out.println(M/2+1);
			median=sc.nextInt();
			System.out.print(median+" ");
			
			for(int i=2;i<=M;i++) {
					n=sc.nextInt();
					
					if(median>n) max_heap.add(n);
					else if(median<n) min_heap.add(n);
					else max_heap.add(n);
					
					
					if(i%2!=0) {
						
						while(max_heap.size()!=min_heap.size()) getMedian();
						System.out.print(median+" ");
						//System.out.println("median "+ median);
				
					}	
				}
				System.out.println();
				
			}
				
	}
	
	

	static void getMedian() {
		int temp;
		if(max_heap.size()<min_heap.size()) {
			temp=min_heap.poll();
			max_heap.add(median);
			median=temp;
		}
		
		else if(max_heap.size()>min_heap.size()) {
			temp=max_heap.poll();
			min_heap.add(median);
			median=temp;
		}
		
	}
		
}