중앙줄기
n 개의 정수 배열 arr이 제공됩니다. 각 인덱스 i (0과 n-1 포함)에 대해 output[i]가 arr[0 .. i] 요소의 중앙값(median)이 되도록 output 배열을 계산합니다.
정수 배열의 중앙값(median)은 다음과 같이 정의됩니다.
- 홀수의 정수가 있는 경우, 중앙값은 정렬된 순서에서 중간 정수와 같습니다.
- 그렇지 않으면 짝수의 정수가 있으면, 중앙값은 정렬된 순서에서 가장 중간에 있는 두 정수의 평균과 같습니다.
- 평균값이 정수가 아닐 경우 가장 가까운 정수로 내립니다 (Floor).
예제 1
입력
arr = [5, 15, 1, 3]
출력
[5, 10, 5, 4] // [5]의 중앙값은 5, // [5, 15]의 중앙값은 (5 + 15) / 2 = 10, // [5, 15, 1]의 중앙값은 5, // [5, 15, 1, 3]의 중앙값은 (3 + 5) / 2 = 4입니다.
예제 2
입력
arr = [1, 2]
출력
[1, 1] // [1]의 중앙값은 1이고 // [1, 2]의 중앙값은 (1 + 2) / 2 = 1.5 // (1로 내림해야 함)입니다.