숫자 리스트와 윈도우 크기 k가 주어졌을 때, 슬라이딩 윈도우 방식으로 각 위치의 중앙값(median) 목록을 구하는 문제입니다. 예를 들어 다음과 같은 배열이 있다고 가정해 보겠습니다.
| 윈도우 위치 | 중앙값 | ||||||||
|---|---|---|---|---|---|---|---|---|---|
| 1 | 3 | -1 | -3 | 5 | 3 | 6 | 8 | 1 | |
| 1 | 3 | -1 | -3 | 5 | 3 | 6 | 8 | -1 | |
| 1 | 3 | -1 | -3 | 5 | 3 | 6 | 8 | -1 | |
| 1 | 3 | -1 | -3 | 5 | 3 | 6 | 8 | 3 | |
| 1 | 3 | -1 | -3 | 5 | 3 | 6 | 8 | 5 | |
| 1 | 3 | -1 | -3 | 5 | 3 | 6 | 8 | 6 | |
위 표에서 주황색으로 표시된 부분이 현재 윈도우에 포함된 요소들입니다. 여기서 k는 3이며, 최종 결과는 [1, -1, -1, 3, 5, 6]이 됩니다. 즉, 윈도우가 한 칸씩 오른쪽으로 이동할 때마다 해당 구간의 중앙값을 계산하여 순서대로 저장하는 것입니다.
해결 접근 방법
이 문제를 효율적으로 해결하려면 정렬된 상태를 유지하면서 삽입과 삭제가 빠른 자료구조가 필요합니다. C++의 multiset은 자동으로 정렬되며 중복 값을 허용하기 때문에 이 문제에 적합합니다. 알고리즘은 다음과 같은 단계로 진행됩니다.
- 정렬된 집합(arr) 역할을 할 multiset을 하나 정의합니다.
- insert(x) 함수: x를 arr에 삽입합니다.
- delete_(x) 함수: x가 존재하면 arr에서 삭제합니다.
- getMedian() 함수:
- n := arr의 크기
- a := arr의 첫 번째 원소에서 n/2 - 1칸 앞으로 이동한 값
- b := arr의 첫 번째 원소에서 n/2칸 앞으로 이동한 값
- arr의 크기가 홀수이면 b를 반환
- 짝수이면 (a + b) * 0.5를 반환
- 메인 메서드에서는 다음을 수행합니다.
- 결과를 담을 배열 ans를 정의하고 arr을 초기화합니다.
- i := 0부터 i < k까지 반복하며 insert(nums[i])를 호출해 첫 번째 윈도우를 채웁니다.
- i := k, j := 0부터 i가 nums 크기 미만일 때까지 i와 j를 1씩 증가시키며 반복합니다.
- getMedian()의 반환값을 ans 끝에 추가
- delete_(nums[j]) 호출로 왼쪽 끝 원소 제거
- insert(nums[i]) 호출로 새로운 원소 추가
- 마지막 윈도우의 중앙값을 ans에 추가한 후 반환합니다.
multiset의 next() 함수를 활용하면 정렬된 컨테이너에서 임의 위치의 원소에 O(n) 시간에 접근할 수 있고, 삽입과 삭제는 O(log n)에 처리되므로 전체적으로 효율적인 솔루션이 됩니다.
예제 코드
아래 구현을 통해 더 잘 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
multiset <double> arr;
void insert(double x){
arr.insert(x);
}
void delete_(double x){
arr.erase(arr.find(x));
}
double getMedian(){
int n = arr.size();
double a = *next(arr.begin(), n / 2 - 1);
double b = *next(arr.begin(), n / 2);
if(arr.size() & 1)return b;
return (a + b) * 0.5;
}
vector<double> medianSlidingWindow(vector<int>& nums, int k) {
vector <double> ans;
arr.clear();
for(int i = 0; i < k; i++){
insert(nums[i]);
}
for(int i = k, j = 0; i < nums.size(); i++, j++){
ans.push_back(getMedian());
delete_(nums[j]);
insert(nums[i]);
}
ans.push_back(getMedian());
return ans;
}
};
main(){
Solution ob;
vector<int> v = {1,3,-1,-3,5,3,6,8};
print_vector(ob.medianSlidingWindow(v, 3));
}입력
{1,3,-1,-3,5,3,6,8}출력
[1, -1, -1, 3, 5, 6]