[boj] 백준 1655 가운데를 말해요 (C++) - heap

[문제]

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

1655번: 가운데를 말해요

 

[풀이]

이런 접근방식은 도대체 어떻게 생각해내는건지...?!

 

최대힙과 최소힙을 구현하여 해결할 수 있다.

값을 넣을 때 다음 두가지 조건을 만족해야한다.

1. 최대힙의 크기는 최소힙의 크기와 같거나 '1'만큼 더 커야한다.

2. 최대힙의 top은 최소힙의 top과 같거나 더 작아야 한다. 

최대힙의 top값이 순서대로 입력될 때의 중간값이 된다.

 

1, 5, 2, 10, -99, 7, 5 가 차례대로 삽입된다고 했을 때,

1) 1 이 들어오면 최대힙의 크기가 최소힙보다 커야하므로 최대힙에 삽입한다. (최대힙 top 1)

2) 5가 들어오면 최대힙의 크기와 최소힙의 크기가 2만큼 차이나지 않도록 최소힙에 삽입한다. (최대힙 top 1)

3) 2가 들어오면 최대힙의 크기가 최소힙보다 커야하므로 최대힙에 삽입한다. (최대힙 top 2)

4) 10이 들어오면 최대힙의 크기와 최소힙의 크기가 2만큼 차이나지 않도록 최소힙에 삽입한다. (최대힙 top 2)

5) -99가 들어오면 최대힙의 크기가 최소힙보다 커야하므로 최대힙에 삽입한다. (최대힙 top 2)

6) 7이 들어오면 최대힙의 크기와 최소힙의 크기가 2만큼 차이나지 않도록 최소힙에 삽입한다. (최대힙 top 2)

5) 5가 들어오면 최대힙의 크기가 최소힙보다 커야하므로 최대힙에 삽입한다. (최대힙 top 5)

 

직접 해보면 다음 2가지 조건이 중간값을 찾기 위한 필수 요건이라는게 느껴진다.

위의 예시에서는 2번째 조건이 나와있지 않지만 만약 최대힙에 2, 최소힙에 -1이 순서대로 삽입되었다면 중간값은 -1이 출력되어야 하므로 두 top의 값을 swap해야한다.

 

[코드]

 

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <cstring>

using namespace::std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int n;
    cin >> n;

    priority_queue<int> max;
    priority_queue<int, vector<int>, greater<int>> min;

    for(int i=0; i<n; i++){
        int num;
        cin >> num;
        if( max.size() == min.size() )
            max.push(num);
        else min.push(num);

        if (!max.empty() && !min.empty() && max.top() > min.top() ) {
            int mt = max.top();
            int nt = min.top();
            max.pop();
            min.pop();
            min.push(mt);
            max.push(nt);
        }

        cout << max.top() << "\n";

    }
}