https://www.acmicpc.net/problem/1655
매번 입력마다 정렬해서 가운데 값을 출력하면 시간초과가 난다ㅜㅜ
0.1초안에 해결해야하는데, 최대 입력이 100,000이므로 O(N^2)으로는 해결할 수 없다는 뜻이다.
이 문제는 2개의 우선순위 큐를 활용하면 되는데, 활용조건은 다음과 같다.
1. 최소 힙의 값들은 모두 최대 힙보다 커야한다.
2. 최대 힙의 크기가 최소 힙의 크기보다 1보다 크거나 같도록 유지한다.
3. 최대 힙과 최소 힙의 top 값을 비교해서 최소 힙의 top보다 최대 힙의 top이 더 크다면 값을 교환해준다.
위 3가지 조건을 잘 지키면, 최대 힙의 top값이 중간값이 된다.
왜 저걸 지켜야하냐??
1번 조건부터 살펴보자. 아래 그림을 보면 이해가 쉬울 것이다.
이런 느낌으로 문제를 풀 것이기 때문에, 당연히 최소 힙의 값들은 최대 힙의 값들보다 커야한다.
그렇지만 실제로 중간 값을 밖으로 따로 빼서 풀진 않을 것이다!
2번 조건을 살펴보자.
- 최대 힙과 최소 힙의 크기가 같은 경우 = "백준이가 외친 수의 개수가 짝수 개인 경우"
ex) 1 2 3 4 5 6
이 때 최대 힙은 {1,2,3}, 최소 힙은 {4,5,6}
- 최대 힙이 최소 힙보다 크기가 1 큰 경우 = "백준이가 외친 수의 개수가 홀수 개인 경우"'
ex) 1 2 3 4 5
이 때 최대 힙은 {1,2,3}, 최소 힙은 {4,5}
어느 상황에서든 최대 힙의 top을 출력하면 중간 값이 나오도록 해주는 조건들이 1,2번 조건인 것이다
3번 조건을 살펴보자
항상 숫자가 예쁘게 주어지는 것은 아니다.
만약 5 0이라는 숫자를 백준이가 외쳤다고 해보자.
그럼 이때의 최대 힙엔 {5}가 들어가있고, 최소 힙엔 {0}이 들어가 있을 것이다.
위 상황은 1,2번 규칙에 위반되는 상황이다!
이를 방지하기 위해 각 힙의 top을 비교해서 최대 힙의 top이 최소 힙의 top보다 크면 두 힙의 top을 바꿔주는 것이다.
-> 그렇게 되면 깔끔하게 정렬된다.
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
int N,num;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N;
priority_queue<int> max_pq; // 작은 수들을 넣는 큐
priority_queue<int,vector<int>,greater<>> min_pq; // 큰 수들을 넣는 큐
// 최소 힙의 값들은 최대 힙의 값들보다 무조건 커야한다! == swap해주자!
// 그리고 최대 힙의 크기는 최소 힙보다 1보다 크거나 같아야한다. == 최대 힙에 값을 먼저 넣어주자!
while (N--) {
cin >> num;
if (max_pq.size() == min_pq.size()) { // 사이즈가 같으면
max_pq.push(num); // 최대 힙에 넣는다 -> why? mid가 2개일 경우 더 작은 수를 출력해야하기 때문
}
else {
min_pq.push(num);
}
if (!max_pq.empty()&&!min_pq.empty()&&max_pq.top()>min_pq.top()) {
// 둘다 비어있지않고, 작은 값들 중 최대 값이 큰 값들 중 최소 값보다 크면
// 두 힙의 top을 swap 해준다!
int max_val, min_val;
max_val = max_pq.top();
min_val = min_pq.top();
max_pq.pop();
min_pq.pop();
max_pq.push(min_val);
min_pq.push(max_val);
}
cout << max_pq.top() << '\n';
}
}
'알고리즘 > 백준(BOJ)' 카테고리의 다른 글
[백준/C++] 17404번 RGB거리2 (0) | 2022.09.29 |
---|---|
[백준/C++] 6087번 레이저 통신 (0) | 2022.09.29 |
[백준/C++] 10830번 행렬 제곱 (0) | 2022.09.29 |
[백준/C++] 1987번 알파벳 (0) | 2022.09.29 |
[백준/C++] 19948번 음유시인 영재 (0) | 2022.09.29 |