[Algospot] 알고스팟 RUNNINGMEDIAN 변화하는 중간값

출처:  https://algospot.com/judge/problem/read/RUNNINGMEDIAN

Approach

[그래프] 힙(Heap) 자료구조란? 

힙(Heap) 자료구조란?

높은 수를 우선순위로 하는 것과 낮은 수를 우선순위로 하는 것, 총 2개의 우선순위 큐 이용

※우선순위 큐는 Heap 구조로 이루어져 있으므로 maxHeap, minHeap으로 변수명 설정

 

새로운 데이터를 입력 받을 때,

조건 [1]. 최대 힙의 크기는 최소 힙의 크기와 같거나, 하나 더 크다.

               따라서, maxHeap.size() == minHeap.size()인 경우 우선적으로 Max Heap에 push

조건 [2]. 최대 힙의 최대 원소(Root Node)는 최소 힙의 최소 원소(Root Node)보다 작거나 같다.

               즉, maxHeap.top() ≤ minHeap.top()이지 않으면 두 Heap의 최상단 노드를 바꿔줍니다.

▶ 조건[1], [2]를 만족한 상태에서 중간값은 최대힙의 최대 원소에 해당

이는 숫자들을 정렬한 뒤 앞의 절반을 최대 힙에, 뒤의 절반을 최소 힙에 넣도록 하는 것입니다.

(수열의 길이가 홀수라면 최대 힙에 숫자가 하나 더 들어 있는 상태)

　

시뮬레이션

data = [3 1 5 4 2]를 순서대로 입력

① data = 3 입력

▷ 최대 힙 = [3]

▷ 최소 힙 = []

최대 힙과 최소 힙의 크기가 같으므로 maxHeap에 push

▶ 중간값 = [3]

 

② data = 1 입력

▷ 최대 힙 = [3] → [1]

▷ 최소 힙 = [1] → [3]

최대 힙과 최소 힙의 크기가 다르므로 minHeap에 push

최대 힙의 최대원소 = 3 > 1 = 최소 힙의 최소원소이므로, 최상단 노드 값을 맞교환

▶ 중간값 = [3 1]

 

③ data = 5 입력

▷ 최대 힙 = [5 1] → [3 1]

▷ 최소 힙 = [3] → [5]

최대 힙과 최소 힙의 크기가 같으므로 maxHeap에 push

최대 힙의 최대원소 = 5 > 3 = 최소 힙의 최소원소이므로, 최상단 노드 값을 맞교환

▶ 중간값 = [3 1 3]

 

④ data = 4 입력

▷ 최대 힙 = [3 1]

▷ 최소 힙 = [4 5]

최대 힙과 최소 힙의 크기가 다르므로 minHeap에 push

최대 힙의 최대원소 = 3 ≤ 4 = 최소 힙의 최소원소이므로, 맞교환 x

▶ 중간값 = [3 1 3 3]

 

⑤ data = 2 입력

▷ 최대 힙 = [3 1 2]

▷ 최소 힙 = [4 5]

최대 힙과 최소 힙의 크기가 같으므로 maxHeap에 push

최대 힙의 최대원소 = 3 ≤ 4 = 최소 힙의 최소원소이므로, 맞교환 x

▶ 중간값 = [3 1 3 3 3]

중간값들의 합은 3 + 1 + 3 + 3 + 3 = 13

---

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <functional>
using namespace std;
 
const int MOD = 20090711;
struct RNG {
    // (문제 조건) 난수 생성기
    int seed, a, b;
    RNG(int _a, int _b) :a(_a), b(_b), seed(1983) {}
 
    int next() {
        int result = seed;
        seed = ((seed * (long long)a) + b) % MOD;
        return result;
    }
};
 
 
int runningMedian(int N, RNG rng) {
    priority_queue<int, vector<int>, less<int>> maxHeap;
    priority_queue<int, vector<int>, greater<int>> minHeap;
 
    int result = 0; // 중간값들의 합
    while (N--) {
        // 조건 1: 최대힙과 최소힙의 개수는 동일하거나 최대힙이 하나 더 크다.
        if (maxHeap.size() == minHeap.size()) {
            maxHeap.push(rng.next());
        }
        else {
            minHeap.push(rng.next());
        }
 
        // 조건 2: 최대 힙의 최대 원소는 최소 힙의 최소 원소보다 작거나 같다.
        // 두개의 힙은 비워져 있지 않으면서 최상단 노드(Root Node), Priority Queue에서 top()으로 비교
        if (!minHeap.empty() && !maxHeap.empty() && minHeap.top() < maxHeap.top()) {
            // 최대힙과 최소힙의 최상단 노드를 맞교환
            int a = maxHeap.top(), b = minHeap.top();
            maxHeap.pop(); minHeap.pop();
            minHeap.push(a); maxHeap.push(b);
        }
        // 최대 힙에 있는 최상단 노드가 중간값에 해당되므로 더해줍니다.
        result = (result + maxHeap.top()) % MOD;
    }
    return result;
}
 
int main(void) {
    int C;
    cin >> C;
 
    while (C--) {
        int N, a, b;
        cin >> N >> a >> b;
        RNG generator(a, b);
        cout << runningMedian(N, generator) << endl;
    }
    return 0;
}