[백준]1655_가운데를 말해요

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

Tip

✔ priority_queue 커스텀하는 법

#include <cstdio>
#include <queue>
using namespace std;
 
struct a{
    int start;
    int end;
    int value;
};
 
struct cmp{
    bool operator()(a t, a u){
        return t.value < u.value;
    }
};
 
priority_queue<a,vector<a>,cmp> pq;

Solved

✔ 자료구조 / 우선순위 큐
✔ 최소 힙과 최대 힙으로 중간값 찾기
1. 최소 힙의 값들은 모두 최대 힙보다 크도록하고
2. 최대 힙의 크기가 최소 힙의 크기보다 1 크거나 같도록 유지하며 값을 넣는다.
3. 값을 넣어준 후 최대 힙과 최소 힙의 top 값을 비교해서 최소 힙의 top보다 최대 힙의 top이 더 크다면 값을 교환해준다.
∴그러면 최대 힙의 top값이 중간값이 된다.
(상세 예시는 제일 아래에 적었다.)

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

priority_queue<int> max_pq; //내림차순
priority_queue<int, vector<int>, greater<int>> min_pq; //오름차순
int n;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;

    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        // processing 
        if (min_pq.size() == max_pq.size()) {
            // to max_pq
            max_pq.push(a);
        }
        else {
            // to min_pq
            min_pq.push(a);
        }
        if (!min_pq.empty() && !max_pq.empty() && min_pq.top() < max_pq.top()) {
            int min_value = min_pq.top();
            min_pq.pop();
            int max_value = max_pq.top();
            max_pq.pop();
            max_pq.push(min_value);
            min_pq.push(max_value);
        }
        //min_pq.top() < max_pq.top()   ==> 바꾼다.. 
        // print
        cout<<max_pq.top()<<'\n';
    }
    return 0;
}

중간값 찾기 예시

1 5 2 10 -99 7 6을 순차적으로 입력받을 때

max heap : 1
min heap : 

max heap : 1
min heap : 5

max heap : 1, 2
min heap : 5 

max heap : 1, 2
min heap : 5, 10

max heap : -99, 1, 2
min heap : 5, 10

max heap : -99, 1, 2
min heap : 5, 7, 10

max heap : -99, 1, 2, 6
min heap : 5, 7, 10

!교환발생
max heap : -99, 1, 2, 5
min heap : 6, 7, 10

결과: 중간값은 max heap의 top인 5.