[ LeetCode ] 480. Sliding Window Median

https://leetcode.com/problems/sliding-window-median/

Sliding Window Median - LeetCode

풀이 방법

슬라이딩 윈도우에 속한 값들 중 중간값을 찾는 문제이다. 중간값은 정렬했을 때, 가장 가운데에 있는 값이다. 중간값를 쉽게 찾을 수 있도록 정렬되고, 중복된 원소를 저장할 수 있는 multiset을 사용하자.

 

multiset에 슬라이딩 윈도우에 속하는 값들을 모두 넣고, 그 중 가운데에 있는 원소를 찾는다. 이때, 가운데에 있는 원소를 찾는 것은 슬라이딩 윈도우 크기가 K일 때, O(K)의 시간이 걸린다. 

auto mid = next(mset.begin(), k/2); // O(k)

 

따라서 매번 가운데 원소를 찾는 것이 아니라, 처음 한번만 가운데 원소를 가리키는 iterator를 찾고, 그 다음부터는 새로 추가할 원소 및 삭제할 원소들의 값에 따라 iterator를 적절히 업데이트해나간다. 

// insert
mset.insert(nums[i]);
if(nums[i] < *mid) mid--;
            
// erase
if(nums[i-k] <= *mid) mid++;
mset.erase(mset.lower_bound(nums[i-k]));

새로 추가한 원소가 기존의 중간값보다 작다면, 한칸씩 밀리면서 iterator가 중간보다 오른쪽 위치를 가리키게 될테니 iterator를 감소시킨다. 

원소를 추가할 때

그리고 삭제할 원소가 중간값보다 작거나 같으면 삭제된 후 한칸씩 밀려올테니 미리 iterator를 증가시킨다.

원소를 삭제할 때

 

한편, 슬라이딩 윈도우 크기가 짝수이면 가운데 두 원소의 평균값이 중간값이 되는데, 다음과 같이 계산할 수 있다.

double median = *mid;
if(k % 2 == 0){
    median += *prev(mid, 1);
    median /= 2;
}

 

전체 코드는 여기서 확인할 수 있다.