문제

문제 링크

어떻게 접근할 것인가

  • 최소힙과 최대힙을 두개를 놓고 진행해라
  • 최대힙 앞에 최소힙을 뒤에 아래 그림과 같이 준비해서 최대힙의 max값이 mid를 가지게 한다.
  • 여기에서 포인트는 최대힙의 개수를 최소힙의 개수 + 1개 이하로 맞추는 것이다. 이를 위해 현재 개수를 보고 어느 힙에 넣을지 결정한다.
  • 이렇게 진행하다가 최대힙의 최대값이 최소힙의 최소값보다 커지면 두개를 스왑한다.
  • 과정은 아래와 같다!

사진

코드

#include <cstdio>
#include <queue>

using namespace std;

char buf[1 << 17];

inline char read() {
    static int idx = 1 << 17;
    if (idx == 1 << 17) {
        fread(buf, 1, 1 << 17, stdin);
        idx = 0;
    }
    return buf[idx++];
}
inline int readInt() {
    int sum = 0;
    bool flg = 1;
    char now = read();

    while (now == 10 || now == 32) now = read();
    if (now == '-') flg = 0, now = read();
    while (now >= 48 && now <= 57) {
        sum = sum * 10 + now - 48;
        now = read();
    }

    return flg ? sum : -sum;
}

int main(){
    int n, m;
    n = readInt();
    priority_queue<int, vector<int>, less<int> > pq1;
    priority_queue<int, vector<int>, greater<int> > pq2;
    for(int i = 0; i < n; i++){
        m = readInt();
        if(pq1.size() == pq2.size() + 1)pq2.push(m);
        else pq1.push(m);
        
        if(!pq1.empty() && !pq2.empty() && pq1.top() > pq2.top()){
            int temp = pq2.top(); pq2.pop();
            pq2.push(pq1.top()); pq1.pop();
            pq1.push(temp);
        }
        printf("%d\n", pq1.top());
    }
}

느낀점

  • 두개의 힙을 사용해서 중간 값을 찾아내는 방법은 정말 신박하다…
  • 나도 이런 생각이 떠오를 수 있었으면 좋겠다. 그래도 아이디어를 구현해낸 것에 만족한다.