[PS] 백준 1655번 가운데를 말해요

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

숫자가 차례대로 하나씩 주어지고, 주어질 때마다 주어진 숫자 와 이전에 주어진 숫자의 중간값을 구하는 문제이다.

최소힙과 최대힙 두개를 이용해서 풀이하였다.
아래의 형태가 정렬된 상태로 유지되게 하면 되겠다.

(최대힙) 중간 값 (최소힙)

힙의 삽입/삭제 연산은 O(logn) 이므로 100,000의 입력에 대해서도 통과가 가능하다. 다른 풀이법이 있을 것 같은데...?

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.StringTokenizer;

class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static Scanner sc = new Scanner(System.in);
	
	static StringTokenizer st;
	
	int n;
	PriorityQueue<Integer> lpq;
	PriorityQueue<Integer> rpq;

	public static void main(String[] args) throws IOException {
		Main ps = new Main();	
		
		ps.solution();
	}

	void solution() throws IOException {
		n = Integer.parseInt(br.readLine());
		lpq = new PriorityQueue<>(Collections.reverseOrder());
		rpq = new PriorityQueue<>();

		
		int input = Integer.parseInt(br.readLine());
		int curMid = input;
		lpq.add(input);
		System.out.println(curMid);
		
		for (int i = 1; i < n; i++) {
			input = Integer.parseInt(br.readLine());
			
			if (lpq.size() == rpq.size()) {
				if (input <= curMid) {
					lpq.add(input);
					curMid = lpq.peek();
				} else {
					rpq.add(input);
					curMid = rpq.peek();
				}
			} else if (lpq.size() < rpq.size()) {
				if (input <= curMid) {
					lpq.add(input);
					curMid = lpq.peek();
				} else {
					lpq.add(rpq.poll());
					rpq.add(input);
					curMid = lpq.peek();
				}
			} else if (lpq.size() > rpq.size()) {
				if (input <= curMid) {
					rpq.add(lpq.poll());
					lpq.add(input);
					curMid = lpq.peek();
				} else {
					rpq.add(input);
					curMid = lpq.peek();
				}
			}
			
			bw.append(Integer.toString(curMid) + '\n');
		}
		bw.flush();
	}
}