boj 2696 : Running Median

boj 2696 : Running Median

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

총 3가지 방법으로 해보았다.

첫번째 : 

가장 단순한 방법으로 

sorting + 중간값 출력...

n * n * logn

역시나 시간초과 ㅎㅎ

두번째 :

selection 알고리즘.

예전에 코드를 직접 짜보았었던게 생각나서 해보았다.

첫번째 방법이 n * n * logn 이라면 이방법은 n * n만에 가능.

직접 짜는것보다 nth_element를 이용..ㅎㅎㅎ 44ms로 AC

세번째 : 

left, right 2개의 힙 이용.

a[i]가 mid보다 클 경우 right에 push, 작거나 같은경우 left에 push.

(작거나 같을 경우나 크거나 같을 경우는 따로 고려해주지 않아도 된다.)

홀수번째마다 3가지 경우의 수가 생긴다.

1. left heap과 right heap의 사이즈가 같은경우.

2. left heap size > right heap size

3. left heap size < right heap size

각각의 경우

1. mid값을 출력.

2. left heap의 top이 mid값. 기존 mid는 right에 push, left heap을 pop.

3. 마찬가지로 right heap의 top이 mid값. 기존 mid는 left에 push하고 right를 pop.

이방법으로 홀수번째마다 left의 size와 right의 크기를 동일하게 유지시킨다.

시간복잡도는 nlogn.

이건 4ms로 AC!!