중앙값 > 문제은행



알고리즘 자료구조2

1570 : 중앙값

제한시간: 1000 ms    메모리제한: 64 MB
해결횟수: 252 회    시도횟수: 509 회   



통계에 있어서 어떤 몇 개의 수들을 대표하는 값으로 자주 사용되는 것에는, 평균(mean), 최빈값(mode), 중앙값(median)이 있다. 이 문제에서 다룰 것은 중앙값(median)으로, 어떤 수들을 오름차순(혹은 내림차순)으로 정렬했을 때 가운데에 오는 값을 그 수들의 중앙값이라고 부른다.

동현이는 N(N은 홀수)개의 공에 각각 적당한 정수를 쓴 후, 그 공들을 상자에 넣었다. 맨 처음에는 한 개의 공을 꺼내고, 그 뒤로부터는 한 번에 두 개의 공을 꺼낸다. 이 때, 꺼낸 공들에 써져 있는 모든 정수들의 중앙값을 구하는 것이 문제이다.

예를 들어, N=7이고, 공에 써져있는 수가 각각 1, 2, 3, 4, 5, 6, 7 이라 하고, 처음에는 5번 공을, 그 뒤로 (1, 2), (7, 4), (6, 3)의 공을 순서대로 꺼냈다고 해보자. 이때 각각의 중앙값들을 구하면 5, 2, 4, 4 가 된다.

[1회] 5
[2회] 1 2 5
[3회] 1 2 4 5 7
[4회] 1 2 3 4 5 6 7

N과 꺼내는 공들이 주어질 때, 각각에 걸쳐 중앙값들을 출력하는 프로그램을 작성하자.


입력의 첫 줄에는 N(3≤N<20,000, 홀수)이 주어지며, 둘째 줄에는 처음에 꺼낸 공에 써져있는 정수가 주어진다.
세 번째 줄부터 (N-1)/2 개의 줄에는 각각 두 개의 정수 P, Q가 주어지는데, 이는 공을 꺼내는 각각의 시행에서 꺼낸 두 개의 공에 써져있는 정수를 의미한다. 입력되는 모든 수는 -30000 이상 30000 이하의 정수이다.



출력은 총 (N+1)/2 줄로 구성되어 있어야 하며 각 줄마다 해당하는 시행까지 꺼낸 모든 공들에 쓰여 있는 정수들의 중앙값을 출력한다.


7
5
1 2
7 4
6 3
5
2
4
4



HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.