[BOJ] 1655. 가운데를 말해요

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

1655번: 가운데를 말해요

값이 계속 들어올 때마다 중간값을 출력해주어야 하기 때문에 매번 정렬을 해서 가운데 값을 출력해주면 시간 초과가 발생한다. 따라서 이 문제는 최대 힙(Max heap)과 최소 힙(Min heap) (우선순위 큐)을 사용하여 풀 수 있다.

 

 

1. 최소 힙의 값들은 모두 최대 힙보다 크도록하고

2. 최대 힙의 크기가 최소 힙의 크기보다 1 크거나 같도록 유지하며 값을 넣는다.

3. 값을 넣어준 후 최대 힙과 최소 힙의 top 값을 비교해서 최소 힙의 top보다 최대 힙의 top이 더 크다면 값을 교환해준다.

그러면 최대 힙의 top값이 중간값이 된다.

 

 

문제의 예제 중 마지막 값인 5를 6으로 수정해서 예를 들어봤다.

1 5 2 10 -99 7 6

위와 같은 값들을 순차적으로 입력받는다고 하면

 

처음에 들어온 1은 max heap에 들어간다. 중간 값은 1

max heap : 1

min heap : 

 

 

다음에 5가 들어오면 max heap의 크기가 더 크므로 min heap에 값이 들어간다.

max heap : 1

min heap : 5

이때, max heap의 top보다 min heap의 top이 크므로 값의 변경은 일어나지 않고, 중간값은 max heap의 top인 1이다.

 

 

그다음에 2가 들어오면 크기가 같으므로 max heap에 들어가고 2는 5보다 작으므로 값의 변경은 일어나지 않는다.

max heap의 top인 2가 중간 값이다.

max heap : 1, 2

min heap : 5

 

 

다음으로 10이 들어오면 min heap의 크기가 더 작으므로 min heap에 들어가고 중간 값은 max heap의 top값인 2이다.

max heap : 1, 2

min heap : 5, 10

 

 

-99는 두 heap의 사이즈가 같으므로 max heap에 들어가고 중간 값은 2이다.

max heap : -99, 1, 2

min heap : 5, 10

 

 

7은 min heap으로 들어간다. 중간 값은 그대로 2이다.

max heap : -99, 1, 2

min heap : 5, 7, 10

 

 

마지막으로 6은 두 heap의 사이즈가 같으므로 max heap에 들어간다.

max heap : -99, 1, 2, 6

min heap : 5, 7, 10

 

이때, max heap의 top인 6이 min heap의 top인 5보다 크므로 두 값을 교환해주어야 한다.

max heap : -99, 1, 2, 5

min heap : 6, 7, 10

교환해주고 나면 max heap의 top인 5가 중간값이 된다.

 

 

 

c++에서 우선순위 큐는 기본적으로 최대 힙이기 때문에 최대 힙은 그냥 우선순위 큐를 하나 만들어주면 되고

최소 힙은 functionl을 include 해준후

 priority_queue<int, vector<int>, greater<int>> minheap;

이런 식으로 greater를 이용해서 만들어주면 된다.

 

처음에는 minheap에 값이 없으므로 top값을 가져올 수 없으므로 maxheap에만 값을 추가하고 다시 다른 값을 입력받도록 처리해주어야 한다. 아니면 top값을 비교할 때 minheap이 비어있는지를 검사해줘도 된다.

#include<iostream>
#include <functional>
#include <queue>
using namespace std;
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    priority_queue<int> maxheap;
    priority_queue<int, vector<int>, greater<int>> minheap;
 
    int n;
    cin >> n;
 
    int x;
    for (int i = 0; i < n; i++) {
        cin >> x;
 
        //처음에 값이 없는 경우
        if (maxheap.size() == 0) {
            maxheap.push(x);
        }
        else {
 
            //최대 힙의 크기가 더 크다면 최소 힙에 값을 넣는다.
            if (maxheap.size() > minheap.size()) {
                minheap.push(x);
            }
            else {
                //크기가 같다면 최대 힙에 넣는다.
                maxheap.push(x);
            }
 
            //최대 힙의 top의 값(최댓값)이 최소 힙의 최솟값보다 크다면 값을 교환한다.
            if (maxheap.top() > minheap.top()) {
                int maxtop = maxheap.top();
                int mintop = minheap.top();
                maxheap.pop();
                minheap.pop();
                maxheap.push(mintop);
                minheap.push(maxtop);
            }
 
        }
        
 
        //중간값을 출력
        cout << maxheap.top() << '\n';
    }
 
    
 
    return 0;
}