728x90
문제
https://www.acmicpc.net/problem/1655
문제이해
- 첫째 줄에 정수의 개수(N)을 입력합니다.
- 다음 줄부터 N개의 수를 입력합니다.
- N번의 케이스 동안의 중간값을 N개의 줄을 통해 출력합니다.
문제 자체의 내용은 매우 간단하지만 시간 제한이 0.1초이기 때문에 무엇인가 색다른 방법이 필요합니다. 처음엔 priority_queue 한개에 자료를 넣고 중간 값을 찾아가 이를 vector에 저장하고 나중에 출력하는 방법을 사용했습니다. 그러나 이렇게 하면 priority_queue의 중간 값을 찾기 위해 O(n)의 시간복잡도를 가지게 되고 시간초과가 날 수 밖에 없었습니다. 도저히 방법이 생각나지 않아 힌트를 보고 풀었고 해답은 다음과 같았습니다.
- priority_queue를 두개 준비합니다. 하나는 max_heap이고 다른 하나는 min_heap입니다.
- max_heap의 top값이 배열의 중간값이 되도록 합니다.
- max_heap의 top값이 배열의 중간값이 되도록 하기위해서는 max_heap의 크기가 min_heap의 크기보다 1 크거나 같아야 합니다.
- 만약 max_heap의 top 값이 min_heap의 top 값보다 크다면 두 값을 바꿔 총 배열이 오름차순이 되도록 수정해줘야 합니다.
다음은 위의 해답으로 만든 코드 입니다.
문제해결
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
priority_queue<int, vector<int>> max_;
priority_queue<int, vector<int>, greater<int>> min_;
vector<int> store;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N, D;
cin >> N;
for (int i{ 0 }; i < N; i++) {
cin >> D;
store.push_back(D);
}
for (int i{ 0 }; i < N; i++) {
D = store[i];
if (max_.size() == min_.size() + 1) {
min_.push(D);
}
else {
max_.push(D);
}
if (max_.size() != 0 && min_.size() != 0) {
if (max_.top() > min_.top()) {
int A = max_.top();
int B = min_.top();
max_.pop();
min_.pop();
max_.push(B);
min_.push(A);
}
}
cout << max_.top() << "\n";
}
}
문제후기
배열을 두개로 나누어 저장한다는 점을 생각하지 못해 한참을 헤맸습니다.
728x90
'Coding' 카테고리의 다른 글
[C++]백준 1644번: 소수의 연속합 (0) | 2023.07.14 |
---|---|
[C++]백준 2075번: N번째 큰 수 (0) | 2023.07.13 |
[C++]백준 1406번: 에디터 (0) | 2023.07.12 |
[C++]백준 5430번: AC (0) | 2023.07.11 |
[C++]백준 2258번: 정육점 (0) | 2023.07.11 |