가운데를 말해요

코드

#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <set>
#define ll long long
using namespace std;
int N;
priority_queue<int, vector<int>, greater<int>> minPQ; // 최소 힙
priority_queue<int, vector<int>, less<int>> maxPQ; // 최대 힙
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N;
    for(int i=0;i<N;i++)
    {
        int a;
        cin >> a;
        /*  입력 개수가 홀수일 때 --> 중간값은 maxHeap에 존재 
            입력 개수가 짝수 일 때 --> 중간값은 minHeap에 존재 */
        /* 조건: 1) maxPQ.size() >= minPQ.size() 
                2) maxPQ.top() <= minPQ.top() 을 만족해야 한다*/
        // maxPQ부터 번갈아 가면서 값을 넣는다                
        if(maxPQ.size() == minPQ.size()){
            maxPQ.push(a);
        }else{
            minPQ.push(a);
        }
        /* maxPQ.top() <= minPQ.top()을 어긋나면 바꿔주어야 한다 */
        // 예시입력 -> {-1, 1}
        if(!maxPQ.empty() != 0 and !minPQ.empty() and maxPQ.top() > minPQ.top()){
            int maxVal = maxPQ.top(); maxPQ.pop();
            int minVal = minPQ.top(); minPQ.pop();
            maxPQ.push(minVal);
            minPQ.push(maxVal);
        }
        cout << maxPQ.top()<< '\n';
    }
    return 0;
}

• 로직
  • 2개의 우선순위 큐(최대힙-maxPQ, 최소힙-minPQ)을 생성
  • maxPQ 부터 시작해서 번갈아가면서 값을 넣는다
  • 만약 maxPQ.top() <= minPQ.top() 을 만족하지 않으면 값을 swap한다
    : 최대힙 큐의 top은 항상 최소힙 큐의 top보다 작아야 함

• 느낀 점
  • 논리적으로 유추하듯 풀어낼 수 는 없는 문제였다
  • 두개의 우선순위 큐를 통해 중간값을 O(N)보다 작은 시간으로 구하는 방법이 있다는 것 정도만 인지

• 자세한 설명 및 참조
  : https://yabmoons.tistory.com/478