[Jungol] 정올 1570 중앙값

출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=843&sca=4020

Approach

힙(Heap) 자료구조란?

- 첫 입력을 mid로 중앙값이라고 하자.

- 우선순위 큐로 maxpq와 minpq 생성 (각각 최대힙과 최소힙)

- 첫 수 이후 들어오는 두 개의 수에 대하여 

    mid 보다 작으면 maxpq / mid 보다 크다면 minpq에 담습니다.

 

 

① 두 pq 크기가 같다면 mid 값 출력

 

② maxpq.size() < minpq.size() 인 경우 mid를 maxpq에 push하고 

    minpq.top()을 새로운 mid값으로 하고 minpq.pop() 수행

    → 새로운 mid 출력

 

③ maxpq.size() > minpq.size() 인 경우 mid를 minpq에 push하고 

    maxpq.top()을 새로운 mid값으로 하고 maxpq.pop() 수행

    → 새로운 mid 출력

 

---

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
 
int N, mid;
const int LM = 20005;
bool max(int a, int b) { return a > b; }
bool min(int a, int b) { return a < b; }
void swap(int& a, int& b) { int t = a; a = b; b = t; }
 
struct PriorityQueue {
    int heap[LM], hn;
    bool (*cmp)(const int, int);
    void init(int order) {
        hn = 0;
        cmp = order ? max : min;
    }
 
    int top() { return heap[1]; }
    int size() { return hn; }
    void push(int data) {
        heap[++hn] = data;
        int c = hn;
        for (int c = hn; c > 1 && cmp(heap[c], heap[c / 2]); c /= 2)
            swap(heap[c], heap[c / 2]);
    }
    void pop() {
        int p = 1, c = 2;
        swap(heap[1], heap[hn--]);
        for (; c <= hn; p = c, c *= 2) {
            if (c < hn && cmp(heap[c + 1], heap[c])) c++;
            if (!cmp(heap[c], heap[p])) break;
            swap(heap[c], heap[p]);
        }
    }
}maxpq, minpq;
 
void push(int data) {
    if (data < mid) maxpq.push(data);
    else minpq.push(data);
}
 
int main() {
    // freopen("input.txt", "r", stdin);
    scanf("%d %d", &N, &mid);
    int i, x, y;
    maxpq.init(1), minpq.init(0);
    printf("%d\n", mid);
 
    for (int i = 0; i < N / 2; ++i) {
        scanf("%d %d", &x, &y);
        push(x); push(y);
 
        if (maxpq.size() > minpq.size()) {
            minpq.push(mid);
            mid = maxpq.top();
            maxpq.pop();
        }
        else if (maxpq.size() < minpq.size()) {
            maxpq.push(mid);
            mid = minpq.top();
            minpq.pop();
        }
        printf("%d\n", mid);
    }
    return 0;
}

 

 

Priority_Queue STL 사용

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <queue>
using namespace std;
int N, mid;
priority_queue<int> minpq, maxpq;
 
void push() {
    int val;
    scanf("%d", &val);
    if (val < mid) maxpq.push(val);
    else minpq.push(-val);
}
 
int main() {
    // freopen("input.txt", "r", stdin);
    scanf("%d %d", &N, &mid);
    printf("%d\n", mid);
    for (int i = 0; i < N / 2; ++i) {
        push(); push();
        if (maxpq.size() < minpq.size()) {
            maxpq.push(mid);
            mid = -minpq.top();
            minpq.pop();
        }
        else if (maxpq.size() > minpq.size()) {
            minpq.push(-mid);
            mid = maxpq.top();
            maxpq.pop();
        }
        printf("%d\n", mid);
    }
    return 0;
}