23.3 문제: 변화하는 중간 값(ID: RUNNINGMEDIAN)
문제
한 수열의 중간값(median)은 이 수열을 정렬했을 때 가운데 오는 값입니다. 예를 들어 {3,1,5,4,2}를 정렬했을 때 가운데 오는 값은 3이지요. 수열의 길이가 짝수일 때는 가운데 있는 두 값 중 보다 작은 것을 수열의 중간값이라고 정의하도록 합시다.
한 수열의 중간값은 수열에 새로운 수가 추가될 때마다 바뀔 수 있습니다. 텅 빈 수열에서 시작해서 각 수가 추가될 때마다 중간값을 계산하는 프로그램을 작성하세요. 예를 들어 3, 1, 5, 4, 2 순서대로 숫자가 추가될 경우 수열의 중간값은 3, 1, 3, 3, 3 순서로 변화합니다.입력 생성
입력의 크기가 큰 관계로, 이 문제에서는 수열을 입력받는 대신 다음과 같은 식을 통해 프로그램 내에서 직접 생성합니다.
- A[0] = 1983
- A[i] = (A[i-1] * a + b) % 20090711
a와 b는 입력에 주어지는 상수입니다. 이 문제의 해법은 입력을 생성하는 방식과는 아무 상관이 없습니다.입력
입력 파일의 첫 줄에는 테스트 케이스의 수 C (1 <= C <= 20)가 주어지고, 그 후 C줄에 각 3개의 정수로 수열의 길이 N (1 <= N <= 200,000), 그리고 수열을 생성하는 데 필요한 두 정수 a , b (0 <= a,b <= 10000) 가 주어집니다.
출력
각 테스트 케이스마다 한 줄에 N개의 중간값의 합을 20090711로 나눈 나머지를 출력합니다.
예제 입력
3 10 1 0 10 1 1 10000 1273 4936예제 출력
19830 19850 2448920
First Thoughts
배열에서 중간값 구하기
무작위로 생성된 숫자를 배열에 정렬하며 삽입한다. 각 입력마다 정렬된 배열에서 중간값을 찾아 총 합을 구한다. 배열의 크기가 짝수일 때는 중간에 있는 두 수 중 더 작을 값을 중간값으로 한다.
My Code
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector <long long> heap;
long long median(vector<long long>& heap) {
long long m = heap.size();
if (m % 2 == 0) {
long long r = m / 2 - 1;
long long l = m / 2;
if (heap[r] < heap[l])
return heap[r];
else
return heap[l];
}
else {
m = m / 2;
return heap[m];
}
}
long long newValue(long long N,long long a, long long b) {
long long sum = 0;
long long start = 1983;
for (long long i = 0; i < N; i++) {
if (i == 0)
heap.push_back(start);
else {
start = (a*start+b)%20090711;
heap.push_back(start);
}
sort(heap.begin(), heap.end());
sum += median(heap);
}
return sum % 20090711;
}
int main(void) {
int C;
int i;
long long N,a,b;
cin >> C;
for (i = 0; i < C; i++) {
cin >> N >> a >> b;
cout << newValue(N, a, b)<< endl;
heap.clear();
}
}Answer Code
#include <iostream>
#include <vector>
#include <queue>
#include <functional>
#include <algorithm>
using namespace std;
struct RNG {
int seed, a, b;
RNG(int _a, int _b):a(_a),b(_b),seed(1983){}
int next() {
int ret = seed;
seed = ((seed * (long long)a) + b) % 20090711;
return ret;
}
};
int runningMedian(int n, RNG rng) {
priority_queue<int, vector<int>, less<int>> maxHeap;
priority_queue<int, vector<int>, greater<int>> minHeap;
int ret = 0;
//최대 힙의 크기는 최소 힙의 크기와 같거나, 하나 더 크다.
//최대 힙의 최대 원소는 최소 힙의 최소 원소보다 작거나 같다
for (int cnt = 1; cnt <= n; cnt++) {
if (maxHeap.size() == minHeap.size())
maxHeap.push(rng.next());
else
minHeap.push(rng.next());
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);
}
ret = (ret + maxHeap.top()) % 20090711;
}
return ret;
}
int main(void) {
int C;
int N, a, b;
cin >> C;
for (int i = 0; i < C; i++) {
cin >> N >> a >> b;
RNG rng(a, b);
cout << runningMedian(N, rng) << endl;
}
}Difference & Faults
시간 초과
코드를 제출해보지 않고도 컴파일 했을 때에도 몇 초의 지연 후에 결과가 나오더라. 그래서 시간초과가 뜰 줄은 알았다. 자료형을 long long으로 바꿔보고 cin,cout을 scanf,printf로도 바꿔봤지만 속도에 크게 영향을 미치진 않더라. 그래서 결국은 내 코드의 시간적 결함을 인정하게 되었다.
부트리 2개 만들기
숫자들을 정렬했을 때 앞의 절반은 최대 힙(maxheap)에 저장하고 뒤의 절반을 최소 힙(minheap)에 저장한다. 힙의 크기가 홀수라면 최대 힙에 숫자를 하나 더 넣도록 한다. 이것을 두개의 문장으로 표현해보면 다음과 같다.
1. 최대 힙의 크기는 최소 힙의 크기와 같거나 하나 더 크다
2. 최대 힙의 최대 원소는 최소 힙의 최소 원소보다 작거나 같다
위 두 문장을 염두에 두고 두개의 힙을 사용하여 숫자를 입력해간다. 그리고 중간값을 항상 최대 힙의 루트에 위치한다.
Impressions
책의 해답을 보기 전에 구글링을 해보니 runningmedian이라는 문제가 꽤나 유명한 문제라는 것을 알게 됬다. 특히 우선순위 큐와 힙에서는 대표적인 연습문제 같았다. 그래서 몇가지 유튜브 영상을 참고하였는데 모든 영상이 하나같이 똑같은 풀이더라. 책도 같은 풀이일까 싶어서 책을 보았는데 역시나 같은 풀이더라. 두 개의 힙을 사용하여 처음에는 두 개 힙의 크기에 따라 입력이 들어가는 숫자의 힙이 다르고 입력된 후 각 힙의 루트 원소의 크기를 비교하여 힙을 수정한다.
Summary
"우선순위 큐와 힙"에서는 꽤나 유명한 문제같아서 문제와 풀이 방법을 기억하고 두고두고 사용해야할 거 같다.
