BOJ 1572, 9426 : 중앙값 측정

알고리즘 문제 전체 링크

 

https://www.acmicpc.net/problem/1572

https://www.acmicpc.net/problem/9426

 

참고

- 구간 합 구하기 with 탑 다운 세그먼트 트리 (Top-Down Segment Tree)
- 구간 합 구하기 with 바텀 업 세그먼트 트리 (Bottom-Up Segment Tree)

- BOJ 1655 : 가운데를 말해요 with 세그먼트 트리

 

 

BOJ 1655 : 가운데를 말해요 with 세그먼트 트리에서 세그먼트 트리를 이용해 가운데 값을 찾았으므로,

이 방법을 이용해 중앙값을 측정해보자.

 

주어지는 숫자가 0 ~ 65535이기 때문에 65536 * 2개의 tree가 필요하다.

또한 세그먼트 트리는 index가 1로 시작하도록 구현을 하였으므로,

값을 넣을 때는 1을 추가하고, 값을 누적할 때는 1을 빼서 더한다.

 

K개의 수를 먼저 세그먼트 트리에 반영한다.

for (int i = 0; i < K; i++) update(arr[i] + 1, 1);

 

그리고 가운데 값을 더한다.

더한 후에는 앞에 있는 수를 빼야하므로 update에 -1를 뺀다.

sum = 0;
sum += (getMid(half) - 1);
update(arr[0] + 1, -1);

 

그리고 다시 update에 값을 넣고, 가운데 값을 구하고 다시 앞의 값을 뺀다.

for (int i = K; i < N; i++)
{
	update(arr[i] + 1, 1);
	sum += (getMid(half) - 1);
	update(arr[i - K + 1] + 1, -1);
}

 

전체 코드는 다음과 같다.

#include <stdio.h>

typedef long long int ll;

int N, K;
int arr[250100];
ll tree[131072];
int start, leafSize;

void update(int index, int diff)
{
	index += start;

	while (index > 1)
	{
		tree[index] += diff;
		index /= 2;
	}
}

ll getMid(int index)
{
	int treeIdx = 1;
	while (treeIdx < leafSize)
	{
		if (index <= tree[treeIdx * 2]) treeIdx *= 2;
		else
		{
			index -= tree[treeIdx * 2];
			treeIdx = treeIdx * 2 + 1;
		}
	}

	return treeIdx - start;
}

int main()
{
	int half, value;
	ll sum;

	scanf("%d %d", &N, &K);
	
	half = (K + 1) / 2;

	for (int i = 0; i < N; i++) scanf("%d", &arr[i]);

	start = 65536 - 1;
	leafSize = 65536;

	for (int i = 0; i < K; i++) update(arr[i] + 1, 1);
	
	sum = 0;
	sum += (getMid(half) - 1);
	update(arr[0] + 1, -1);

	for (int i = K; i < N; i++)
	{
		update(arr[i] + 1, 1);
		sum += (getMid(half) - 1);
		update(arr[i - K + 1] + 1, -1);
	}

	printf("%lld\n", sum);

	return 0;
}

---

Top-Down 방식은 다음과 같다.

#include <stdio.h>

typedef long long int ll;

int N, K;
int arr[250100];
ll tree[131072];
int start, leafSize;

void update(int left, int right, int node, int index, int diff)
{
	if (index < left || right < index) return;

	tree[node] += diff;

	if (left != right)
	{
		int mid = (left + right) / 2;

		update(left, mid, node * 2, index, diff);
		update(mid + 1, right, node * 2 + 1, index, diff);
	}
}

int getMid(int left, int right, int node, int value)
{
	if (left == right) return left;

	int mid = (left + right) / 2;

	if (value <= tree[node * 2]) return getMid(left, mid, node * 2, value);
	else return getMid(mid + 1, right, node * 2 + 1, value -= tree[node * 2]);
}

int main()
{
	int half, value;
	ll sum;

	scanf("%d %d", &N, &K);
	
	half = (K + 1) / 2;

	for (int i = 0; i < N; i++) scanf("%d", &arr[i]);

	start = 65536 - 1;
	leafSize = 65536;

	for (int i = 0; i < K; i++) update(1, 65536, 1, arr[i] + 1, 1);
	
	sum = 0;
	sum += (getMid(1, 65536, 1, half) - 1);
	update(1, 65536, 1, arr[0] + 1, -1);

	for (int i = K; i < N; i++)
	{
		update(1, 65536, 1, arr[i] + 1, 1);
		sum += (getMid(1, 65536, 1, half) - 1);
		update(1, 65536, 1, arr[i - K + 1] + 1, -1);
	}

	printf("%lld\n", sum);

	return 0;
}