23.3_변화하는 중간값_RUNNINGMEDIAN

문제 설명

 

algospot.com :: RUNNINGMEDIAN

• 중간값 = 수열을 정렬했을 때 가운데 오는 값.
• 수열의 길이가 짝수일 경우, 가운데 있는 두 값 중 작은 것을 중간값으로 한다.
• 텅 빈 수열에 각 수가 추가될 때마다 중간값을 계산하는 프로그램을 만든다.

=> 각 중간값의 합을 20090711로 나눈 나머지 출력하기

 

문제 풀이

일반적인 중간값 구하기

특별한 자료구조 없이 중간값을 구한다고 하면,

1. 수열을 입력받는다.
2. 정렬한다.
3. 배열의 길이/2 위치의 값을 구한다 = 중간값.

N개의 수가 입력된다고 했을때 정렬을 N번 수행해야 하므로

퀵정렬과 같은 빠른 정렬을 수행했을 때에도 O(N * NlogN)의 시간복잡도가 나온다.

 

중간값만 구하기

우리가 이 문제에서 원하는 것은 오직 중간값이기 때문에,

중간값 앞의 수와 뒤의 수의 정렬은 굳이 필요하지 않다.

 

따라서 수열을 [앞 수열(이하 frontArr) | 뒷 수열(이하 backArr)]으로 분리하고

frontArr이 backArr과 크기가 같거나(수열 길이 짝수) 1개 크도록(수열 길이 홀수) 구현한다면

frontArr 중 가장 큰 값이 이 수열의 중간값이 될 것이다.

 

Priority Queue를 이용하여 frontArr, backArr 만들기

수열에 수가 추가될 때 frontArr에 넣어야 할지, backArr에 넣어야 할지 판단하기 위해서는

frontArr의 가장 큰 수와 backArr의 가장 작은 수가 필요하다.

위의 두 수와 비교하여 새로 추가된 수가 frontArr로 갈지, backArr로 갈지 판단이 가능하기 때문이다.

 

Descending Priority Queue, Ascending Priority Queue를 구현하여

아래 그림과 같이 'Descending Priority Queue' = frontArr, 'Ascending PriorityQueue' = backArr으로 사용한다면,

각 큐의 top을 frontArr의 가장 큰 수, backArr의 가장 작은 수로 사용할 수 있다.

추가된 값을 PQ에 넣어준 후, 크기 비교를 통해 같거나, frontArr이 1크도록 조정해주면

frontArr의 top이 중간값이 된다.

 

 

이 방식은 한 숫자에 대해 Priority Queue의 push 시간 복잡도인 O(logN)만 소요되므로

전체 O(NlogN)의 시간복잡도를 가지게 된다.

 

 

문제 풀이 코드

#include <iostream>

using namespace std;

// 우선순위큐 구현
class PriorityQueue {
private:
	bool ascd = false;	// 오름차순 여부
	int size = 0;
	int arr[20000];

public:
	PriorityQueue(bool ascd) {
		size = 0;
		this->ascd = ascd;
		fill_n(arr, 20000, 0);
	}

	int getSize() {
		return size;
	}

	int getTop() {
		return arr[1];
	}

	void pop() {
		if (!size) return;
		int num = arr[size];
		arr[size] = 0;
		--size;
		int idx = 2;
		while (idx <= size) {
			if (idx + 1 <= size) {
				if ((ascd && arr[idx] > arr[idx + 1]) || (!ascd && arr[idx] < arr[idx + 1]))
					++idx;
			}
			if ((ascd && num > arr[idx]) || (!ascd && num < arr[idx])) {
				arr[idx / 2] = arr[idx];
				idx *= 2;
			}
			else break;
		}
		arr[idx/2] = num;
	}

	void push(int num) {
		size++;
		int idx = size;
		while (idx > 1) {
			if ((ascd && num < arr[idx / 2]) || (!ascd && num > arr[idx / 2])) {
				arr[idx] = arr[idx / 2];
				idx = idx / 2;
				continue;
			}
			break;
		}
		arr[idx] = num;
	}
};

int main() {
	int C;
	cin >> C;
	for (int tc = 1; tc <= C; ++tc) {
		int N;
		long long a, b;
		cin >> N >> a >> b;
		PriorityQueue frontPq(false);		// 앞 우선순위큐
		PriorityQueue backPq(true);		// 뒤 우선순위큐
		long long num = 1983;
		int sum = 1983;
		frontPq.push(num);			// 처음 값 넣기
		for (int n = 1; n < N; ++n) {
			num = (num * a + b) % 20090711L;
			if (frontPq.getTop() < num) {	// num이 앞 우선순위큐의 top 보다 크면
				backPq.push(num);
			}
			else {
				frontPq.push(num);	// num이 앞 우선순위큐의 top 보다 작으면
			}
			
            		// 앞 우선순위큐의 크기가 뒷 우선순위 큐의 크기와 같거나 1 크도록 유지
			if (backPq.getSize() > frontPq.getSize()) {
				frontPq.push(backPq.getTop());
				backPq.pop();
			}
			else if (backPq.getSize() + 1 < frontPq.getSize()) {
				backPq.push(frontPq.getTop());
				frontPq.pop();
			}
			sum += frontPq.getTop();
			sum %= 20090711L;
		}
		cout << sum << endl;
	}
	return 0;
}