1655 가운데를 말해요

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

1655번: 가운데를 말해요

 

최대 힙과 최소 힙 둘 다 사용하여, 작은 쪽 반은 최대 힙에 저장하고, 큰쪽 반은 최소 힙에 저장하여 해결할 수 있는 문제이다.

 

처음 문제를 보고 힙을 쓸 생각은 했지만, 힙 2개를 사용할 생각을 못했다.

 

힙을 써야겠다고 생각한 이유

문제에서 어떤 입력값이 주어질 때마다 정렬을 해야하는 경우 (다수 그리디 문제에서 이런 문제가 있음.) 힙을 써야한다고 생각했다.

 

이 문제에서는 어떤 입력값이 주어질 때마다 정렬을 해야하긴 하지만, 힙의 경우 중간값을 꺼낼 수 없기에 힙을 2개를 써야한다.

그래서 작은 쪽 반은 최대힙, 큰쪽 반은 최소 힙을 사용해서 중간값을 뽑아낸다.

입력된 숫자가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말하면 되므로 최대힙쪽에서 출력하도록 하면 된다.

 

 

 

#include <bits/stdc++.h>
 
using namespace std;
 
#define swap(a,b) (a)^=(b)^=(a)^=(b)
#define endl '\n'
typedef long long lld;
 
int main()
{
    cin.sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int n;
    cin >> n;
    priority_queue<int, vector<int>, greater<int>> mn_heap;
    priority_queue<int, vector<int>, less<int>> mx_heap;
    
    int tmp;
    for(int i=0;i<n;i++)
    {
        cin >> tmp;
        mx_heap.push(tmp);
        while(!mn_heap.empty() && mx_heap.top() > mn_heap.top())
        {
            tmp = mn_heap.top();
            mn_heap.pop();
            mn_heap.push(mx_heap.top());
            mx_heap.pop();
            mx_heap.push(tmp);
        }
        tmp = (mx_heap.size()+mn_heap.size())%2;
        while(mx_heap.size() > mn_heap.size()+tmp)
        {
            mn_heap.push(mx_heap.top());
            mx_heap.pop();
        }
        cout << mx_heap.top() << endl;
    }
    return 0;
}