1655 c++ - 가운데를 말해요

우선순위 큐를 사용하는 문제.

처음에는 우선순위 큐, vector의 정렬 중간값을 사용해서 풀이를 진행했는데, 시간초과가 났습니다.
그래서 우선순위 큐 두개를 사용하여 최대힙, 최소힙을 사용하여 풀었습니다.

 

vector<int> v;

  for (int i = 0; i < n; ++i) {
    int t;
    cin >> t;
    v.push_back(t);

    sort(v.begin(), v.end(), less<int>());

    cout << v[i / 2] << "\n";
  }

#include <iostream>
#include <queue>

#define FASTIO ios::sync_with_stdio(0), cin.tie(0)
using namespace std;

int n;

int main() {
  FASTIO;

  cin >> n;

  priority_queue<int, vector<int>, greater<int>> pq;
  queue<int> q;

  for (int i = 0; i < n; i++) {
    int t;
    cin >> t;
    pq.push(t);
    for (int j = 0; j < i / 2; j++) {
      q.push(pq.top());
      pq.pop();
    }
    cout << pq.top() << "\n";
    for (int j = 0; j < i / 2; j++) {
      pq.push(q.front());
      q.pop();
    }
  }
  return 0;
}

 

시간 복잡도는 O(Nlog⁡N)이 된다.

정답 코드

#include <iostream>
#include <queue>

#define FASTIO ios::sync_with_stdio(0), cin.tie(0)
using namespace std;

int n;
int main() {
  FASTIO;
  cin >> n;

  priority_queue<int> maxHeap;
  priority_queue<int, vector<int>, greater<int>> minHeap;

  for (int i = 0; i < n; ++i) {
    int t;
    cin >> t;

    if (maxHeap.empty() || t <= maxHeap.top()) {
      maxHeap.push(t);
    } else {
      minHeap.push(t);
    }

    if (maxHeap.size() > minHeap.size() + 1) {
      minHeap.push(maxHeap.top());
      maxHeap.pop();
    } else if (minHeap.size() > maxHeap.size()) {
      maxHeap.push(minHeap.top());
      minHeap.pop();
    }

    cout << maxHeap.top() << "\n";
  }

  return 0;
}