[BOJ/Platinum 5] 백준 1572 중앙값(C++)

문제 링크

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

1572번: 중앙값

 

문제

중앙값이란, 수열을 정렬했고, 그 크기가 N일 때, 1부터 시작해서 (N+1)/2번째 있는 원소가 그 수열의 중앙값이다. 예를 들어, {1, 2, 6, 5, 4, 3}에서는 3이고, {11, 13, 12, 15, 14}에서는 13이다.

오세준은 1초에 온도를 하나씩 재는 온도계를 만들었다. 이 온도계에는 작은 디스플레이 창이 하나 있는데, 이 창에는 지금부터 최근 K초 까지 온도의 중앙값을 표시해 준다. (온도를 재기시작한지 K초부터 표시한다. 그 전에는 아무것도 출력되지 않는다.)

오세준은 온도를 N초동안 쟀다. 그 시간 동안 온도계의 디스플레이 창에 뜨는 숫자의 합을 구하는 프로그램을 작성하시오.

다른 말로 하면, 길이가 N인 수열이 주어진다. 이 수열은 N-K+1 개의 길이가 K인 연속된 부분 수열이 존재한다. 이 부분 수열의 중앙값의 합을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. N은 250,000보다 작거나 같은 자연수이고, K는 5,000보다 작거나 같은 자연수이다. N은 항상 K보다 크거나 같다. 둘째 줄부터 N개의 수가 한 줄에 하나씩 주어진다. 입력으로 주어지는 수는 65536보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 정답을 출력한다. 정답은 263-1보다 작거나 같다.

예제 입력 1

10 3
3
4
5
6
7
8
9
10
11
12

예제 출력 1

60

예제 입력 2

5 2
10
13
13
13
13

예제 출력 2

49

예제 입력 3

7 3
4123
19382
23581
23040
1743
18362
60593

예제 출력 3

102186

알고리즘 분류

• 자료 구조

풀이

이 문제와 비슷한 문제다.

9426번: 중앙값 측정

온도의 개수가 최대 25만개나 되기 때문에 N-K+1개의 수열들의 중앙값을 1초 안에 다 파악하기가 힘들다. 따라서 세그먼트 트리를 이용하는데, 풀이가 떠오르지 않아 구글을 이용하였다.

1. 우선 0번째 수부터 K-1개의 수를 세그먼트 트리에 업데이트한다. 이 때, 세그먼트 트리에는 해당 구간에 속해 있는 온도들의 개수가 존재하게 된다.

2. 그리고 K번째 수를 업데이트한다. 그러면 K개의 수에 대한 정보가 세그먼트 트리에 업데이트되며, 중앙값은 (K+1)/2라고 하였으므로, (K+1)/2를 값으로 가지는 구간이 나올 때까지 계속 탐색하는데, 찾는 값이 현재 구간의 중앙값보다 작으면 왼쪽 자식을, 크면 오른쪽 자식을 탐색한다. 

3. 2번 과정을 N-K+1번 반복한다.

그림으로 보면 더 쉽게 이해할 수 있다. 본인은 하도 이해가 안 돼서 이 글을 참고하였다.

[BOJ] 백준 1572번 중앙값 (Java)

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 1000001
#define LL long long
#define ULL unsigned long long
#define MAXV 65535
#define INF 1e9

using namespace std;
ULL N, K;
ULL Tree_Height, Tree_Size;
ULL SegTree[MAX];
ULL MAP[MAX];
ULL answer = 0;

void Input() {
	cin >> N >> K;
	for (int i = 0; i < N; i++) {
		cin >> MAP[i];
	}
}

void Make_SegTree(ULL Node, ULL S, ULL E, ULL VAL, ULL DIFF) {
	// 세그먼트 트리에서의 VAL은 온도를 의미한다. 이분 탐색을 통하여 온도의 개수를 누적시킨다.
	if (S == E) {
		SegTree[Node] += DIFF;
		return;
	}
	ULL MID = (S + E) / 2;
	if (VAL <= MID) {
		Make_SegTree(Node * 2, S, MID, VAL, DIFF);
	}
	else {
		Make_SegTree(Node * 2 + 1, MID + 1, E, VAL, DIFF);
	}
	SegTree[Node] = SegTree[Node * 2] + SegTree[Node * 2 + 1];
}

ULL Find_Value(ULL Node, ULL S, ULL E, ULL VAL) {
	if (S == E) {
		return S;
	}
	ULL MID = (S + E) / 2;
	if (VAL <= SegTree[Node * 2]) {
		return Find_Value(Node * 2, S, MID, VAL);
	}
	else {
		return Find_Value(Node * 2 + 1, MID + 1, E, VAL - SegTree[Node * 2]);
	}
}

void Settings() {
	for (int i = 0; i < (K - 1); i++) { // 0번째 수부터 K-1개의 수를 세그먼트 트리에 업데이트시킨다.
		Make_SegTree(1, 0, MAXV, MAP[i], 1);
	}
}

void Find_Answer() {
	int IDX = 0;
	for (int i = (K - 1); i < N; i++) {
		Make_SegTree(1, 0, MAXV, MAP[i], 1);
		answer += Find_Value(1, 0, MAXV, (K + 1) / 2);
		Make_SegTree(1, 0, MAXV, MAP[IDX++], -1);
	}
	cout << answer << "\n";
}

int main() {
	FASTIO
	Input();
	Settings();
	Find_Answer();

	return 0;
}