(C++) - 백준(BOJ) 1655번 : 가운데를 말해요

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

1655번: 가운데를 말해요

우선순위 큐 문제였습니다.

 

풀이방법

* 입 출력이 많으므로 c와 동기화를 끊어줘야 합니다. 제 소스코드의 #define의 fastio 참고하세요.

 

 최대 힙, 최소 힙 이렇게 두 개의 우선순위 큐를 선언해줍니다. 이 두개로 중앙값을 찾기 위해 규칙을 세웁니다.

1. 최대 힙과 최소 힙의 원소 개수가 같다면 최대힙에 push를 먼저해줍니다. 

2. 최소 힙의 원소들은 최대 힙의 원소 이상으로 큽니다.

 

이런식으로 넣었을 때 최대힙에는 최소힙의 원소보다 큰 값이 들어가 1번 규칙을 위배할 수 있습니다. 이 경우 즉, 만약 maxHeap의 가장 큰 원소(top())가 minHeap의 가장 작은 원소(top())보다 크다면 서로의 자리를 바꿔주어 서순에 혼동이 오지 않도록 합니다.

 

이 규칙을 지켰을 때 예제를 가지고 시뮬레이션한다면 다음과 같습니다. 

, 5, 2, 10, -99, 7, 5

 

수빈이가 외치는 첫 번째 숫자 1

규칙 1,2에 의거 다음과 같습니다.

maxHeap : [ 1 ]

minHeap : [ ]

 

수빈이가 외치는 두 번째 숫자 5

1번 규칙에 의해 push 된 이후

maxHeap : [ 1 ]

minHeap : [ 5 ]

 

수빈이가 외치는 세 번째 숫자 2

1번 규칙에 의해 push 된 이후

maxHeap : [ 2, 1 ]

minHeap : [ 5 ]

 

수빈이가 외치는 네 번째 숫자 10

1번 규칙에 의해 push 된 이후

maxHeap : [ 2, 1 ]

minHeap : [ 5, 10 ]

 

수빈이가 외치는 다섯 번째 숫자 -99

1번 규칙에 의해 push 된 이후

maxHeap : [ 2, 1, -99 ]

minHeap : [ 5, 10]

 

수빈이가 외치는 여섯 번째 숫자 7

1번 규칙에 의해 push 된 이후

maxHeap : [ 2, 1, -99 ]

minHeap : [ 5, 7, 10]

 

수빈이가 외치는 일곱 번째 숫자 8

1번 규칙에 의해 push 된 이후

maxHeap : [ 8, 2, 1, -99 ]

minHeap : [ 5, 7, 10]

 

2번 규칙에 의해 서순이 바뀌었으므로 minHeap top과 maxHeap top을 교환. 결과

maxHeap : [ 5, 2, 1, -99 ]

minHeap : [ 7, 8, 10]

 

이렇게 한 번 시뮬레이션을 해본다면 중앙값은 항상 maxHeap의 top임을 알 수 있습니다.

 

Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
int n, mid;
priority_queue <int,vector<int>> maxHeap;
priority_queue <int,vector<int>,greater<int>> minHeap;

int main(){
    fastio;
    cin >> n;
    for(int i = 1; i <= n; i++){
        int num; 
        cin >> num;
        if(maxHeap.size() == minHeap.size()) maxHeap.push(num);
        else minHeap.push(num);
        if(minHeap.size() && maxHeap.size() && maxHeap.top() > minHeap.top()){
            int maxVal = maxHeap.top();
            int minVal = minHeap.top();
            maxHeap.pop(), minHeap.pop();
            minHeap.push(maxVal);
            maxHeap.push(minVal);
        }
        cout << maxHeap.top() << '\n';
    }
}