알고리즘 문제해결전략(문제 ID: RUNNINGMEDIAN)

OvO·2020년 8월 2일
0

문제해결전략

목록 보기
9/16

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

🤔생각

이번 챕터가 우선순위 큐와 힙에 대한 것이었으므로 힙으로 풀어야 될 거 같았다. 그래서 수열을 추가하면서 히프정렬로 수열을 정렬하면서 중간값을 찾으려고 했다. 하지만 이 방법은 N^2log(N)이어서 시간초과가 날 거 같았다. 그렇게 생각을 더 해보다가 방법이 떠오르지 않아서 책을 봐버렸다. 이 책에서는 주어진 수열을 두 묶으으로 나눈다. 한 묶음에는 정렬된 수열에서의 앞의 절반, 뒤의 절반 이렇게 말이다. 그리고 이를 통해 두 가지의 불변식을 도출해내고 이를 활용한다.

😀코드

#include<iostream>
#include<queue>
#include<algorithm>

using namespace std;

int A[200001], N;

void makeSequence(int a, int b) {
	int i = 2;
	A[1] = 1983;

	while (i <= N) {
		A[i] = ((long long)A[i - 1] * a + b) % 20090711;
		i++;
	}
	
}

int runningMedian(int n) {
	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(A[cnt]);
		else
			minHeap.push(A[cnt]);

		if (!maxHeap.empty() && !minHeap.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, a, b;
	int ret = 0;

	cin >> C;
	while (C--) {
		cin >> N >> a >> b;
		makeSequence(a, b);

		printf("%d\n", runningMedian(N));
	}
}

👏후기

중간값을 찾으려고 할 때 나는 정렬을 한 다음에 특정 인덱스에 접근 함으로써 답을 찾으려 했지만 시간초과로 실패하였다. 이 책에서는 중간값보다 작은 부류, 중간 값보다 큰 부류를 나눔으로써 빠르게 중간값을 찾을 수 있었다.

profile
이유재입니다.

0개의 댓글