[백준] 자바 문제 풀이 2696 : 골드2

BOJ 2696 : 중앙값 구하기 풀이 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer str = new StringTokenizer(br.readLine(), " ");
		int T = Integer.parseInt(str.nextToken());

		Queue<Integer> rst = new LinkedList<>();
		PriorityQueue<Integer> min_queue = new PriorityQueue<>();
		PriorityQueue<Integer> max_queue = new PriorityQueue<>((o1, o2) -> (o2-o1));
		
		for (int t = 0; t < T; t++) {
			int n = Integer.parseInt(br.readLine());	
			rst.clear();
			min_queue.clear();
			max_queue.clear();
			
			for(int i = 1; i <= n; i++) {
				if((i-1) % 10 == 0)
					str = new StringTokenizer(br.readLine(), " ");
				
				if(min_queue.size() == max_queue.size()) {
					min_queue.add(Integer.parseInt(str.nextToken()));
				}
				else {
					max_queue.add(Integer.parseInt(str.nextToken()));
				}
				
				if(!min_queue.isEmpty() && !max_queue.isEmpty()) {
					if(min_queue.peek() < max_queue.peek()) {
						int tmp = min_queue.poll();
						min_queue.add(max_queue.poll());
						max_queue.add(tmp);
					}
				}
				
				if(i % 2 == 1) {
					rst.add(min_queue.peek());
				}

			}
			
			System.out.println(rst.size());
			int cnt = 1;
			while(!rst.isEmpty()) {
				System.out.print(rst.poll() + " ");
				if(cnt++ % 10 == 0)
					System.out.println();
			}
			System.out.println();
		}

	}

}