BOJ 1655 가운데를 말해요

 

 

 

BOJ 백준 1655 C++

가운데를 말해요

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

 

0) 처음에는 이중 for문 이용해서 N^2시간에 구하려고 했는데 직관적으로 시간초과가 예상되었다(N이 최대 10만)

1) priority queue를 이용한 두개의 heap을 통해 중간값을 구할 수 있다.

2) [조건 1] pqLeft의 크기는 pqRight와 같거나, 1 크다

    [조건 2] pqLeft.top() 의 값은 -pqRight.top() 보다 항상 작다.

       -> 크기가 같을 때, left에 push하므로 push 후 top을 확인하여, 재정렬 필요

 

*****

문제에 주어진 <예제 입력1> 실행 시 pqLeft, pqRight에 실제 들어있는 값

pqLeft  : 기본 우선순위 큐 사용, 내림차순  정렬 (가장 큰 값이 top)

pqRight  : 부호(-)를 붙여 오름차순 정렬  (가장 작은 값이 top)

 

pqLeft	pqRight
1
1	-5
2 1	-5
2 1	-5 -10
2 1 -99	-5 -10
2 1 -99	-5 -7 -10
5 2 1 -99	-5 -7 -10

 

각 단위에서 출력되는 pqLeft.top() 값

 

 

/**
 * 200610
 * 1655 가운데를 말해요
 * Priority_queue & Heap
 * */

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

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

    int N;
    cin >> N;

    priority_queue <int> pqLeft, pqRight;
    int x;

    for(int i=1; i<=N; i++){
        cin >> x;
        
        if(pqLeft.size() == pqRight.size())
            pqLeft.push(x);
        else
            pqRight.push(-x);
        
        if(!pqLeft.empty() && !pqRight.empty() && pqLeft.top()> -pqRight.top()){
            int lPush = -pqRight.top();
            int rPush = pqLeft.top();
            pqLeft.pop();
            pqRight.pop();

            pqLeft.push(lPush);
            pqRight.push(-rPush);
        }

        cout << pqLeft.top() << '\n';
    }
    
    return 0;
}