가운데값 말하기
면접 대비시간 제한0.1초메모리 제한128 MB
정수가 하나씩 입력될 때마다 지금까지 입력된 수들의 중앙값(개수가 짝수면 두 중앙값 중 작은 값)을 출력합니다.
문제
정수가 하나씩 주어진다. 정수가 추가될 때마다 지금까지 주어진 모든 수를 정렬했을 때의 가운데값을 출력해야 한다.
지금까지 주어진 수의 개수가 짝수이면 가운데에 있는 두 수 중 더 작은 값을 가운데값으로 정한다. 각 순간의 가운데값을 순서대로 구하는 프로그램을 작성하라.
입력
첫째 줄에 주어지는 정수의 개수 N이 주어진다. 1 <= N <= 100,000이다.
다음 N개의 줄에는 정수가 하나씩 순서대로 주어진다. 각 정수 x는 -10,000 <= x <= 10,000을 만족한다.
출력
N개의 줄에 걸쳐, 각 정수가 주어진 직후의 가운데값을 한 줄에 하나씩 출력한다.