문제

• 
• 시간 제한: 1초
• 메모리 제한: 256MB

Problem Analysis

Naive 하게 풀면, 매번 K 구간에 있는 수들을 정렬하여 (k+1)/2번째 수를 얻을 수 있다. 이 방법은, O(KlogK)를 N-k+1번 반복하게 되므로 시간 복잡도가 너무 크다. 그러나, K 크기의 창을 한 칸씩 옮기는 동안, 맨 앞을 제외한 나머지 K-1개는 계속 유지되므로, 이를 활용하면 좋을 것 같다. Segment Tree로 0부터 65535까지의 각 수의 개수를 저장하면, 이전 정보를 이용하여 문제를 풀 수 있을 것 같다.

Algorithm

1. Update: 가장 오래된 온도를 ST에서 -1 한다
2. Update: 현재 온도를 ST에 +1 한다
3. getMedian: (k+1)/2 번째 수를 찾는다. 이때, 아래의 방법을 따른다

  left ~ mid, mid+1 ~ right 두 구간에 숫자들이 몇 개 있는지 확인한다.
두 구간 중에서, (k+1)/2번째 수가 존재할 수 있는 구간으로 getMedian을 recursive call 한다.

Data Structure

• ST[]: Segment Tree, 0부터 65535까지의 각 수들이 존재하는 개수를 저장

결과

Other

L = 66536이라고 할 때, ST를 update 하고 값을 구하는 데에는, O(logL)이 걸린다. 이를 N-K+1번 반복하므로, 시간 복잡도는 O(NlogL)이다.