백준 1655번

원본 : https://www.acmicpc.net/problem/1655

1655번: 가운데를 말해요

 

풀이

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Comparator;
import java.util.PriorityQueue;

public class Main {

	public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
	public static BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

	public static void main(String[] args) throws Exception {
		int n = Integer.parseInt(reader.readLine());
		
		PriorityQueue<Integer> leftPq = new PriorityQueue<Integer>(new Comparator<Integer>() {
			@Override
			public int compare(Integer o1, Integer o2) {
				return o2 - o1;
			}
		});
		
		PriorityQueue<Integer> rightPq = new PriorityQueue<Integer>(new Comparator<Integer>() {
			@Override
			public int compare(Integer o1, Integer o2) {
				return o1 - o2;
			}
		});
		
		for (int i = 1; i <= n; i++) {
			int input = Integer.parseInt(reader.readLine());
			
			if (i % 2 == 0) {
				leftPq.add(input);
			} else {
				rightPq.add(input);
			}
			
			if (leftPq.peek() != null && rightPq.peek() != null) {
				int leftTop = leftPq.peek();
				int rightTop = rightPq.peek();
				
				if (leftTop > rightTop) {
					leftPq.remove();
					rightPq.remove();
					leftPq.add(rightTop);
					rightPq.add(leftTop);
				}
			}
			
			if (i % 2 == 0) {
				writer.write(leftPq.peek() + "\n");
			} else {
				writer.write(rightPq.peek() + "\n");
			}
		}
		
		writer.flush();
	}
}