[KOITP] 중앙값

출    처 : http://koitp.org/problem/SDS_PRO_3_6/read/

시간 제한	메모리 제한	제출 횟수	정답 횟수 (비율)	정답자 수
1.1 초	512 MB	1754	452 (26%)	379

문제

정수가 N개 주어진다. 홀수번째 수가 주어질 때마다, 지금까지 주어진 수의 중앙값을 구하는 프로그램을 작성하여라.

예를 들어 1, 4, 5, 3, 6가 주어진다면, 첫번째 수인 1을 입력받을 때 중앙값이 1이고, 세 번째 수인 5를 입력받을 때까지의 중앙값이 4이고, 다섯번째 수인 6을 입력받을 때까지의 중앙값이 4이므로 1, 4, 4를 순서대로 출력하는 것이다.

입력

첫 번째 줄에 주어지는 정수의 개수 N이 주어진다. (1 ≤ N ≤ 99,999, N은 홀수)

두 번째 줄부터 N개의 줄에 걸쳐 각 줄에 하나씩 정수가 주어진다. (1 ≤ 주어지는 정수 ≤ 1,000,000,000)

출력

홀수번째 수를 입력받을 때마다 그 때까지 입력받은 정수들의 중앙값을 한 줄에 하나씩 출력한다.

힌트

입력 예제

7
1 
9 
5 
3 
2 
8
8

출력 예제

1
5
3
5

< Comment >

 풀이를 어느정도 알고도 한참을 풀었습니다. 기본적으로 mid 값을 한쪽에서만 뽑는다고 가정하고 진행을 했어야 조금 더 생각하기 편했을 텐데 이러한 가정없이 양쪽 힙에서 뽑은 숫자 중에 큰값 작은값~~ 라는 식으로 생각하다보니 머리가 복잡해져 더욱 오래 걸렸던 것 같습니다. 아이디어는 심플하나 기존에 알고 있지 못하다면 매우 어려운 문제일 수도 있다고 생각됩니다.

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

public class MiddleNumber {

	public static int N = 0;
	public static int arr[] = null;
	
	public static void main(String[] args) throws Exception {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		N = Integer.parseInt(br.readLine());
		
		PriorityQueue<Integer> minHeap = new PriorityQueue<>();
		PriorityQueue<Integer> maxHeap = new PriorityQueue<>();
		
		minHeap.add(Integer.MAX_VALUE);
		maxHeap.add(Integer.MAX_VALUE);
		
		int curr = 0;
		int mid = Integer.parseInt(br.readLine());
		maxHeap.add(-mid);
		bw.write("" + mid + "\n");
		for (int i = 1 ; i < N ; i++) {
			
			mid = -maxHeap.peek();
			curr = Integer.parseInt(br.readLine());
			if (mid >=  curr) {
				maxHeap.add(-curr);
			} else {
				minHeap.add(curr);
			}
			
			if (maxHeap.size() - minHeap.size() > 1) {
				minHeap.add(-maxHeap.poll());
			} else if (minHeap.size() - maxHeap.size() > 0) {
				maxHeap.add(-minHeap.poll());
			}
			
			mid = -maxHeap.peek();
			if (i % 2 == 0) {
				bw.write("" + mid + "\n");
			}
		}
		
		bw.close();

	}
}