실패를 두려워하지 않고
될 때까지 덤비는 🔥
그런 프로그래머 😎

문제
풀이

💡Idea

생각 흐름

  • N = 100’000 = 10^5
  • 처음에는 자료구조를 한 개 쓰는 방법으로 궁리했었는데
    • lgN으로 정렬된 상태로 삽입하고,
    • 중간값으로 임의 접근할 수 있는
    • 그런 자료구조가 애매해서 이 접근은 포기하였다.
      • multiset을 사용하고 iterator로 중간값을 계쏙 잘 가리키게 할 수 있지 않을까 싶은데, 너무 번거롭고 복잡해진다.
  • 그래서 priority_queue 두 개를 이용해서 풀었다.
  • 왼쪽은 max heap, 오른쪽은 min heap을 사용하여, 두 heap의 크기가 같거나 왼쪽이 하나 더 많도록 구현하면 된다.
  • 그러면 새로운 원소 추가 한번 당 O(lgN)의 작업을 1번 혹은 2번으로 끝낼 수있다.
    • 작업이 2번인 경우: 삽입했을 때 두 heap의 크기가 조건을 만족하지 않아서 많은 쪽에서 적은 쪽으로 원소 이동을 한번 더함
  • 즉 총 시간 복잡도는 O(NlgN)으로 구현 가능

    요약

  • max heap(left)와 min heap(right)를 써서 풀면 된다.

    🔑Code

    ```c++ #include <bits/stdc++.h> using namespace std;

int main(void){ ios_base::sync_with_stdio(0); cin.tie(0);

int N;
cin >> N;

priority_queue<int> left; // left.top()이 중간값
priority_queue<int,vector<int>,greater<int>> right;

for(int i = 0; i < N; i++){
    int cur;
    cin >> cur;

    // 중간값보다 작으면 왼쪽, 크면 오른쪽에 보낼 것임
    if(left.empty() || cur <= left.top()) left.emplace(cur);
    else right.emplace(cur);

    // 크기가 불균형 해지면 조정. 왼쪽이 한 더 많아도 됨.
    if(left.size() < right.size()){
        left.emplace(right.top());
        right.pop();
    }
    else if(left.size() > right.size()+1){
        right.emplace(left.top());
        left.pop();
    }
    cout << left.top() << '\n';
}

return 0; } ``` ## 🗨️ Side Notes

참고