백준, BOJ, 1665번, 가운데를 말해요 : C++ [CPP]

어려웠다.

우선순위 큐를 이렇게 이용한다는 것이 나에겐 조금 어려웠다.

시간을 보아하니 절대로 Brute Force, 전수조사는 아니었다.

힌트를 보고나서야 풀 수 있었다.

 

 

 

 

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

 

---

 

 

 

#맞는 풀이

#include <iostream>
#include <bits/stdc++.h>

using namespace std;


int N;


priority_queue<int, vector<int>, greater<int>> minH;
priority_queue<int> maxH;



int main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    
    cin >> N;
    for(int i = 1; i<=N; i++){
        int x;
        cin >> x;
        //min에 넣을지 max에 넣을지??
        //한쪽에만 몰아넣으면 안된다.
        //그렇게 하면 중간값을 바로 알 수 없어서 둘의 사이즈를 항상 차이가 1만큼만 나게 해야한다.
        
        //같거나 min이 크면 max에 넣어줌.
        //즉, 항상 max가 min과 같거나 max가 1이 더 큼
        if(minH.size() >= maxH.size()){
            maxH.push(x);
        }
        //max가 크면 min에 넣어줌.
        else{
            minH.push(x);
        }
        
        //중간값을 max의 top에, min의 top에 항상 놔두기 위해서는
        //min에 들어가는 값은 항상 max에 들어가는 값보다 커야한다.
        if(maxH.size() != 0 && minH.size() != 0){
            if(maxH.top() > minH.top()){
                int tmp1 = maxH.top();
                int tmp2 = minH.top();
                maxH.pop();
                minH.pop();
                maxH.push(tmp2);
                minH.push(tmp1);
            }
        }
        /*
        
        //홀수라면 중간값 존재.
        if(i%2 == 1){
            if(maxH.size()>minH.size()){
                cout << maxH.top() << '\n';
            }else{
                cout << minH.top() << '\n';
            }
        }
        //짝수면 더 작은 것.max top이 더 작게했으므로 maxtop 출력
        else{
            cout << maxH.top() << '\n';
        }
        */
        
        //사실 홀수 짝수를 구분해야했으나
        //항상 max가 더 클때는 중간값이 담겨있고
        //같을 때는 max가 더 작은 값이 담겨있으니
        //이렇게만 해도 된다.
        cout << maxH.top() << '\n';
    }
    
    
    return 0;
}