알고스팟 - 변화하는 중간값 (RUNNINGMEDIAN) 설명

문제 : https://algospot.com/judge/problem/read/RUNNINGMEDIAN

문제에서 설명한 바와 같이 수열에 새로운 값을 삽입할 때마다 해당 수열의 중간값을 출력하는 효율적인 방법은 두 개의 우선순위 큐를 이용하는 것입니다. 두 개의 우선순위 큐 중에서 하나는 오름차순 우선순위 큐, 다른 하나는 내림차순 우선순위 큐로 구성합니다. 새로운 데이터를 삽입할 때, Q1의 top보다 작으면 Q1에 삽입하고, Q2의 top보다 크면 Q2에 삽입하면서, 모든 경우에 대해 만약 Q1과 Q2의 데이터 개수를 동일하거나 전체 데이터 개수가 홀수 개이면서 Q1의 데이터 개수가 Q2보다 한 개 더 많을 때, Q1의 top이 중간값이라고 할 수 있습니다.

예시를 위해 입력 데이터를 다음과 같이 구성하여 순차적으로 삽입하는 과정을 설명드리겠습니다.

첫 번째 데이터 5를 Q1 또는 Q2에 삽입해야 합니다. 우선, Q1의 데이터가 하나도 없으면 해당 데이터를 Q1에 우선적으로 삽입합니다. 현재 상황에서는 Q1과 Q2 통틀어서 데이터가 5밖에 존재하지 않으므로 5가 중간값이라고 할 수 있습니다.

다음으로 데이터 10을 삽입해야 합니다. Q1은 데이터가 적어도 하나는 존재하지만, Q2는 데이터가 하나도 없기때문에 비어있는 큐를 만들지 않기 위해 Q2에 10을 삽입합니다. 문제의 설명에서와 같이 데이터 개수가 짝수 일 때는 중간값이 두 개가 될 수 있는데 그 중에서 더 작은 값을 중간값으로 취한다고 합니다. 따라서, 5가 중간값으로 선택됩니다.

다음으로 25를 삽입해야 합니다. 이제는 Q1과 Q2가 모두 데이터를 하나씩 가지고 있습니다. 이제부터는 Q1의 top과 Q2의 top을 각각 삽입할 데이터와 크기를 비교해야 합니다. 만약 삽입할 데이터가 Q1의 top보다 작다면 Q1에 우선적으로 삽입합니다. 그게 아니라 만약 삽입할 데이터가 Q2의 top보다 크다면 Q2에 삽입합니다. 현재는  25가 Q2의 top인 10보다 크기 때문에 Q2에 삽입을 하게 됩니다. 이때, Q1과 Q2의 데이터 개수 차이는 비록 1밖에 차이가 나지 않지만, 우리는 항상 Q1에서 중간값을 추출하기 위해 Q1과 Q2의 데이터 개수를 동일하게 하거나 Q1이 Q2보다 한 개 더 많도록 항상 유지를 해주어야 합니다.

따라서, 위와 같이 Q2에서 10을 추출한 후에 Q1에 삽입을 하여 Q1이 Q2보다 한 개 더 많은 데이터를 가지도록 구성합니다. 그리고 Q1의 top을 중간값으로 추출합니다.

다음으로, 데이터 15를 삽입해야 합니다. 앞서 설명한 조건과 같이, 삽입할 데이터가 Q1의 top보다 작으면 Q1에 삽입하고, Q2의 top보다 크면 Q2에 삽입해야 합니다. 그러나, 현재 15는 두 조건을 모두 만족하지 않기 때문에 아무 조건없이 Q1에 삽입합니다. 그러나, 현재 Q1의 데이터 개수가 Q2보다 두 개나 많기 때문에 데이터 개수 차이를 1로 만들기 위해 Q1의 top을 추출하여 Q2에 삽입해주어야 합니다.

위의 그림과 같이 15를 Q1으로부터 Q2를 추출하여 데이터 개수를 동일하게 맞추면 Q1의 top이 중간값이라는 것을 알 수 있습니다.

앞서 설명한 조건에 따라 이후의 데이터를 순차적으로 삽입하면 다음과 같은 결과를 얻게됩니다.

최종적으로, 모든 중간값들을 합하면 75의 결과를 얻게됩니다.