[Beakjoon] 1655 가운데를 말해요 (C++)

문제 링크

BOJ 1655: 가운데를 말해요

문제

입력

7
1
5
2
10
-99
7
5

출력

1
1
2
2
2
2
5

풀이

매 입력마다 중앙값이 무엇인지 출력해야한다.
가장 간단히 생각할 수 있는 방법은 배열에 숫자를 추가하고 매 입력마다 정렬하여 가운데 값을 출력하는 것이지만 이러한 방식으로는 제한시간 안에 문제를 해결할 수 없다.

우선순위 큐를 이용한다.
priority_queue 두개를 이용하여 하나는 중앙값부터 중앙값보다 작은 값들을 저장하는 DQ, 다른 하나는 중앙값보다 큰 수를 저장하는 UQ로 정의한다.

1. 입력받는 수 num이 현재 존재하는 중앙값보다 큰 경우 UQ에, 작거나 같을 경우에는 DQ에 삽입한다.

2. UQ와 DQ의 size를 맞춰준다. DQ에서 중앙값을 저장하기 때문에 DQ의 크기는 UQ보다 항상 1 크거나 같아야한다. (총 짝수개의 수들 중 중앙값을 선택할 때는 둘 중 작은 값을 선택하기 때문에 두 우선순위 큐의 크기가 같더라도 DQ에 있는 값이 중앙값이다.)

DQ.size() == UQ.size() 이거나 DQ.size() == UQ.size() + 1 이라면 DQ.top()이 중앙값을 나타낸다.

코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

#define endl "\n"

using namespace std;

int N;
priority_queue<int, vector<int>, greater<int>> UQ;
priority_queue<int> DQ;

void Solve() {
    cin>>N;
    int num;
    for(int i=0; i<N; i++){
        cin>>num;
        if(DQ.empty() || DQ.top()>=num) DQ.push(num);
        else UQ.push(num);
        
        while(DQ.size() < UQ.size()){
            if(UQ.empty()) break;
            DQ.push(UQ.top()); UQ.pop();
        }
        while(DQ.size()-1 > UQ.size()){
            UQ.push(DQ.top()); DQ.pop();
        }
        cout<<DQ.top()<<endl;
    }
}


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

    return 0;
}