BOJ 1655. 가운데를 말해요
랭크 : 골드2
문제 풀이
우선 순위 큐를 두 개 만드는데 하나는 큰 값들이 오름차순으로, 하나는 작은 값들을 내림차순으로 만들어서 두 개의 큐가 계속 크기가 1개 이상 차이나지 않도록 유지하면 작은 값들의 Top이 답이 됩니다.
#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
using namespace std;
int N, tmp;
priority_queue<int> pqlow;
priority_queue<int, vector<int>, greater<int>> pqup;
int main() {
fastio;
cin >> N;
for (int i = 0; i < N; i++) {
cin >> tmp;
if (pqlow.size() == pqup.size()) {
if (!pqup.empty() && tmp >= pqup.top()) {
pqlow.push(pqup.top()); pqup.pop();
pqup.push(tmp);
} else pqlow.push(tmp);
} else {
if (!pqlow.empty() && tmp <= pqlow.top()) {
pqup.push(pqlow.top()); pqlow.pop();
pqlow.push(tmp);
} else pqup.push(tmp);
}
cout << pqlow.top() << "\n";
}
}
알고리즘 |
시간복잡도 |
공간복잡도 |
|---|---|---|
| priority_queue | $O(N log N)$ | $O(N)$ |
'알고리즘 > 백준' 카테고리의 다른 글
| BOJ 11444. 피보나치 수 6 (0) | 2022.07.18 |
|---|---|
| BOJ 11657. 타임머신 (0) | 2022.07.17 |
| BOJ 17298. 오큰수 (0) | 2022.07.17 |
| BOJ 1450. 냅색문제 (0) | 2022.07.17 |
| BOJ 11054. 가장 긴 바이토닉 부분 수열 (0) | 2022.07.17 |