[백준 1655] 알고리즘 104일차 : 가운데를 말해요

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

1655번: 가운데를 말해요

우선순위 큐 C++

하나의 수를 입력할때 마다 저장된 수들 중 중간값을 출력하는 문제

 

접근방법

최대힙과 최소힙을 모두 사용한다는 아이디어를 얻었다.

정렬된 수열을 반 잘라 앞부분은 최대힙에, 뒷부분은 최소힙에 저장해서

최소힙의 루트노드와 최대힙의 루트노드만 참조하여 중간값을 구하는 것이다.

물론 진짜로 반으로 나눠서 넣으면 안되고 입력받을 때마다 둘 중 한 곳에 push해야한다.

 

최대힙 루트노드 <= 최소힙 루트노드 이어야하기 때문에

새로운 값을 넣을때는 루트노드와 크기비교를 해야한다.

 

그리고 두 힙의 크기가 2개 이상 차이나면 안되기 때문에

그럴때마다 많은 쪽 루트노드를 적은쪽으로 옮겨줘야한다.

 

출력할때는 두 힙의 크기를 비교해서 같으면 최대힙 루트노드를

다르면 큰쪽 루트노드 출력

 

이 두가지를 항상 만족해야 한다. 

1. 최대힙과 최소힙의 크기차이는 같거나 1개차이인 상태가 유지되어야 한다.

2. 최대힙의 루트노드의 값이 최소힙의 루트노드의 값보다 항상 작거나 같아야한다.

 

소스코드

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    priority_queue<int, vector<int>, greater<>> min_heap;
    priority_queue<int, vector<int>, less<>> max_heap;

    int N;
    cin >> N;
    
    for(int i = 0 ; i < N ; i++){
        int n;
        cin >> n;
        //n input
        if(max_heap.empty()){
            max_heap.push(n);
        }else{
            if(n < max_heap.top()){
                max_heap.push(n);
            }else{
                min_heap.push(n);
            }
        }
        
        if(max_heap.size() - min_heap.size() == 2){
            min_heap.push(max_heap.top());
            max_heap.pop();
        }else if(min_heap.size() - max_heap.size() == 2){
            max_heap.push(min_heap.top());
            min_heap.pop();
        }
        //peek
        if(max_heap.size() == min_heap.size() || min_heap.size() < max_heap.size()){
            cout << max_heap.top() << "\n";
        }else if(max_heap.size() < min_heap.size()){
            cout << min_heap.top() << "\n";
        }
    }
    
    return 0;
}