냉장 진열대의 기준 신호

문제

한 편의점은 냉장 진열대의 상태를 확인하기 위해 센서 신호를 일정한 간격으로 기록한다. 센서가 보내는 값은 실제 온도 자체가 아니라 장치 내부에서 변환한 정수 신호다. 신호는 음수일 수도 있다. 담당자는 한 번에 모은 N개의 기록에 일시적인 잡음이 섞였는지 확인하고, 정해진 규칙으로 보정한 합계를 재고 관리 장치에 전달하려 한다. 먼저 보정 전의 기록 N개를 값이 작은 순서로 정렬한다고 생각한다. 정렬한 값 중 앞에서 ⌊(N+1)/2⌋번째에 있는 값을 이번 묶음의 기준값 M으로 정한다. 여기서 ⌊x⌋는 x 이하의 가장 큰 정수다. 따라서 기록의 수가 짝수이면 가운데 두 값 중 작은 값을 기준값으로 사용한다. 같은 값이 여러 번 등장하면 각각 별개의 기록으로 세며, 중복된 값을 제거하지 않는다. 잡음을 구분하는 허용 폭은 정수 D로 주어진다. 원래 기록값 x에 대하여 |x-M|이 D보다 크면 그 기록을 이상치로 판정한다. 차이가 정확히 D이면 정상 기록이다. 이상치로 판정한 기록은 값 M으로 바꾸고, 나머지 기록은 원래 값을 유지한다. 모든 기록의 판정에는 처음에 계산한 하나의 기준값 M을 사용한다. 보정한 값을 이용하여 기준값을 다시 구하거나 이상치 여부를 다시 판단하는 과정은 없다. 같은 원래 값이 여러 번 등장하면 각 기록을 따로 판정하므로 이상치의 개수에도 각각 포함된다. 기준값과 같은 기록은 D가 0이어도 정상이며, 정상 기록이 하나도 없을 때의 처리를 별도로 고려할 필요는 없다. 담당자가 확인해야 하는 정보는 기준값, 이상치로 판정한 기록의 개수, 보정이 끝난 전체 기록값의 합이다. 기록을 정렬한 순서나 보정한 각 기록을 출력할 필요는 없다. 주어진 기록과 허용 폭을 이용하여 이 세 값을 구하는 프로그램을 작성한다.

입력

첫째 줄에 정수 N과 D가 공백으로 구분되어 주어진다. 1 ≤ N ≤ 60,000, 0 ≤ D ≤ 18이다.
둘째 줄에 원래 기록값 N개가 공백으로 구분되어 주어진다. 각 기록값은 -9 이상 9 이하의 정수다.

출력

기준값 M, 이상치의 개수, 보정한 전체 기록값의 합을 공백으로 구분하여 한 줄에 출력한다. 이상치가 없으면 개수는 0이며 합은 원래 기록값의 합이다.

7 2
1 2 2 3 9 -3 2

2 2 14

4 0
-2 -2 5 5

-2 2 -8

1 9
-7

-7 0 -7

출처: Devin.KR 자체 제작