슬라이딩 중앙값
실버 I의견: 0
길이 \(N\)의 정수 배열 \(A\)와 홀수인 창 크기 \(K\)가 주어진다. 배열을 왼쪽에서 오른쪽으로 슬라이드하면서 길이 \(K\)인 연속 구간 \(A[i], A[i+1], \dots, A[i+K-1]\)의 중앙값을 구한다. (중앙값이란 그 구간을 정렬했을 때 정확히 \(\frac{K+1}{2}\)번째 원소이다.)
총 \(N - K + 1\)개의 구간에 대해 중앙값을 순서대로 출력하여라.
- \(1 \le K \le N \le 100\,000\)
- \(K\)는 홀수이다.
- 모든 배열 원소는 \(-10^9\) 이상 \(10^9\) 이하의 정수이다.
첫째 줄에 배열의 길이 \(N\)과 창 크기 \(K\)가 공백으로 구분되어 주어진다.
둘째 줄에 배열의 원소 \(N\)개가 공백으로 구분되어 주어진다.
\(N - K + 1\)개의 줄에 걸쳐, \(i\)번째 줄에 \(i\)번째 창의 중앙값을 출력한다.
8 3
3 1 4 1 5 9 2 6
3
1
4
5
5
6
각 창 크기 \(3\) 구간의 중앙값(정렬 후 두 번째 원소)을 구한다. \([3,1,4]\)의 중앙값은 \(3\), \([1,4,1]\)은 \(1\), \([4,1,5]\)는 \(4\), \([1,5,9]\)는 \(5\), \([5,9,2]\)는 \(5\), \([9,2,6]\)는 \(6\)이다.
3 1
7 2 5
7
2
5
\(K=1\)이므로 각 원소 자체가 중앙값이다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
슬라이딩 중앙값
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
슬라이딩 중앙값