문제링크 : https://www.acmicpc.net/problem/1655
이 문제는 우선순위 큐를 사용하여 중간값을 빠르게 찾아내야 하는 문제다.
이 문제를 그저 벡터 하나에 넣고 입력값이 들어올 때마다 벡터를 정렬하여
중간값을 찾아내고자 한다면, 입력값이 10만개 이므로, O(n * nlogn) 즉
약 100,000 * 100,000 * log(100,000) 하여 170,000,000,000 의 연산이 걸린다.
O(n * nlogn)
1초에 1억번 연산을 할 수 있다 치더라도 1700초가 걸린다.
시간제한은 2초이다.
우선순위 큐를쓴다면 nlogn + (n/2)logn(n/2) * 2 이므로
17만 + (5만 * 16 ) * 2 해서 7040000의 연산이 필요하다.
즉, 0.0704초가 걸린다.
알고리즘은 이렇다.
1. Max heap 과 Min heap 두개를 생성한다.
전체 숫자가 있는 정렬된 벡터가 있다고 가정해보자. 이때 중간값 이전(즉, 0번째부터 ~ 중간값)은 인덱스 값이 커질수록 오름차순이다. 우리는 이 부분에서 가장 큰, 중간값 부분의 숫자를 얻고싶다.
중간값 이후 ~ 벡터의 끝 부분도 오름차순이다. 즉, 중간값 부분은 중간값 이후 ~ 벡터 끝 부분에서는 가장 작은 값이다.
Max는 Min의 size보다 같거나 커야 한다.
2. 1의 가정에 비추어, Max의 가장 큰 값은 Min의 가장 작은 값보다 작아야 한다.
이를 위배한다면 Max의 가장 큰 값과 Min의 가장 작은 값을 교환한다.
소스코드 :
이 문제는 우선순위 큐를 사용하여 중간값을 빠르게 찾아내야 하는 문제다.
이 문제를 그저 벡터 하나에 넣고 입력값이 들어올 때마다 벡터를 정렬하여
중간값을 찾아내고자 한다면, 입력값이 10만개 이므로, O(n * nlogn) 즉
약 100,000 * 100,000 * log(100,000) 하여 170,000,000,000 의 연산이 걸린다.
O(n * nlogn)
1초에 1억번 연산을 할 수 있다 치더라도 1700초가 걸린다.
시간제한은 2초이다.
우선순위 큐를쓴다면 nlogn + (n/2)logn(n/2) * 2 이므로
17만 + (5만 * 16 ) * 2 해서 7040000의 연산이 필요하다.
즉, 0.0704초가 걸린다.
알고리즘은 이렇다.
1. Max heap 과 Min heap 두개를 생성한다.
전체 숫자가 있는 정렬된 벡터가 있다고 가정해보자. 이때 중간값 이전(즉, 0번째부터 ~ 중간값)은 인덱스 값이 커질수록 오름차순이다. 우리는 이 부분에서 가장 큰, 중간값 부분의 숫자를 얻고싶다.
중간값 이후 ~ 벡터의 끝 부분도 오름차순이다. 즉, 중간값 부분은 중간값 이후 ~ 벡터 끝 부분에서는 가장 작은 값이다.
Max는 Min의 size보다 같거나 커야 한다.
2. 1의 가정에 비추어, Max의 가장 큰 값은 Min의 가장 작은 값보다 작아야 한다.
이를 위배한다면 Max의 가장 큰 값과 Min의 가장 작은 값을 교환한다.
소스코드 :
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
#include <iostream>
#include <vector>
#include <list>
#include <string>
#include <queue>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
priority_queue<int> maxHeap;
priority_queue<int, vector<int>, greater<int> > minHeap;
int n;
cin >> n;
for (int i = 0; i < n; i++) {
int num;
cin >> num;
if (maxHeap.size() == minHeap.size()) {
maxHeap.push(num);
}
else {
minHeap.push(num);
}
if (!minHeap.empty() && !maxHeap.empty() && minHeap.top() < maxHeap.top()) {
int a = maxHeap.top(), b = minHeap.top();
maxHeap.pop();
minHeap.pop();
maxHeap.push(b);
minHeap.push(a);
}
cout << maxHeap.top() << '\n';
}
}
| cs |
댓글
댓글 쓰기