알고리즘 문제해결 전략 Chapter 23 - RUNNINGMEDIAN(C++)

예제: 변화하는 중간값

한 수열의 중간값(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

풀이

힙 또는 우선순위 큐를 사용하여 푸는 문제이다.. 만!
나에게는 STL이 있기 때문에 망설임없이 priority queue를 사용해준다.

max queue와 min queue 사이에는 중간값이 존재한다는 것을 유의하며 풀면 된다.

물론 필자도 관련 지식을 책을 읽으며 쌓았지만, 막상 풀고나니 이해하기 어렵지 않은 개념인 것 같다.
물론 heap을 구현해서 풀라고 한다면....😅

한가지 유의할 점은, 난수를 생성할 때 int가 표현 가능한 범위를 아득히 넘어버리기 때문에 long long 자료형을 사용해주도록 하자.

전체적인 소스코드는 아래와 같다.

소스 코드

#include<iostream>
#include<queue>
#include<vector>

using namespace std;

int medianSum(vector<long long>& seq) {
	priority_queue<int, vector<int>, less<int>> maxHeap;
	priority_queue<int, vector<int>, greater<int>> minHeap;
	int sum = 0;

	for (int i = 0; i < seq.size(); i++) {
		//maxHeap과 minHeap을 번갈어 넣는다.
		if (i % 2 == 0) maxHeap.push(seq[i]);
		else if (i % 2 == 1) minHeap.push(seq[i]);

		if (!minHeap.empty() && maxHeap.top() > minHeap.top()) {
			int maxTop = maxHeap.top(); maxHeap.pop();
			int minTop = minHeap.top(); minHeap.pop();

			maxHeap.push(minTop);
			minHeap.push(maxTop);
		}

		sum += maxHeap.top();
		sum %= 20090711;
	}

	return sum;
}

int main() {

	int testCase;
	cin >> testCase;

	for (int tc = 0; tc < testCase; tc++) {
		int N, a, b;
		cin >> N >> a >> b;

		vector<long long> seq(N);
		seq[0] = 1983;
		for (int i = 1; i < N; i++) {
			seq[i] = (seq[i - 1] * a + b) % 20090711;
		}

		cout << medianSum(seq) << endl;
	}
	
	return 0;
}

풀이 후기

필자는 for문을 돌려 난수를 생선하는데, 알고리즘 문제해결 전략 도서는 구조체를 선언하여 난수 생성을 하여, 코드를 한결 깔끔하게 한다.

책을 보며 공부하면 이런점이 좋다. 혼자 풀어보는것도 중요하지만, 잘 정리된 이론을 책을 통해 배우는 것도 상당히 유의미한 일이라고 생각한다.