백준 #1572 중앙값(힙)

이번 문제는 N개의 데이터가 들어올 때, K개의 연속된 값 구간의 중앙값을 구해야 하는 문제입니다.

일반적으로 N개의 정렬되지 않은 데이터가 주어졌을 때, 중앙값을 구하는 것을 $O(N)$ 알고리즘으로 가능합니다.

 

N개의 데이터에  K개의 연속된 값 구간은 $N-K+1$개가 존재합니다.  만약, 위의 방법으로 하고자 한다면, $O(NK)$ 알고리즘으로 풀어야 합니다.  그런데 문제에서 N의 최대값을 250,000, K의 최대값은 5,000으로 $O(NK)$ 알고리즘으로 풀게 되면 시간초과가 될 것이 뻔합니다.

 

https://www.acmicpc.net/problem/1572

1572번: 중앙값

 

저는 자료구조를 이용해서 풀었습니다.  두개의 힙을 만들어서 왼쪽은 최대힙으로 오른쪽은 최소힙으로 만듭니다.  힙은 자료의 추가, 루트 삭제가 $O(\log N)$인 알고리즘입니다.  이것을 이용하면 $O(N\log K)$ 알고리즘으로 문제를 풀 수 있습니다.

 

i번째 데이터를 읽은 상태에서, 왼쪽힙(LeftHeap)과 오른쪽힙(RightHeap)이 있다면, i+1번째 데이터 $v_{i+1}$의 값이 중앙값을 기준으로 왼쪽인지 오른쪽인지 판단합니다.  그리고 $v_{i-k+1}$ 데이터값이 중앙값의 왼쪽인지 아닌지 판단합니다. $v_{i+1}$ 값은 추가해야 하고,  $v_{i-k+1}$ 값은 삭제해야 하죠.  추가, 삭제가 한쪽 힙에서만 발생하면, 힙간의 이동을 하지 않지만, 한쪽은 추가, 다른 한쪽은 삭제가 된다면, 힙간의 이동을 통해서 왼쪽힙과 오른쪽힙이 같은 개수가 되도록 합니다.  K값이 홀수인 경우에는 오른쪽힙을 하나 많게 설정을 하도록 합니다.

 

이것이 기본적인 제 생각이었지만, 실제 구현을 위해서는 다음을 고려해야 합니다.  힙은 루트 삭제를 빼고는 중간에 있는 값을 빼는 것이 쉽지 않습니다.  인덱스를 추적하는 방식이 있기는 하겠지만, 근본적으로 그렇게 하기 위해서는 별도의 힙 모듈을 작성해주어야 합니다.  그래서 저는 힙에는 인덱스를 저장하고, 삭제는 이미 만료된 인덱스가 힙의 루트에 있는 경우 삭제토록 했습니다.