[BOJ/Platinum 5] 백준 9426 중앙값 측정(C++)

문제 링크

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

9426번: 중앙값 측정

 

문제

기상학에서 주요 사용하는 대표값은 중앙값이다. (중앙값의 정의는 힌트에 나와있다)

상근이는 1초에 한 번씩 온도를 재는 기계를 가지고 있고, 이 기계에 들어갈 소프트웨어를 작성하려고 한다. 기계에는 작은 디지털 디스플레이가 하나 달려있다. 매 초마다 디스플레이는 지난 K초동안 측정한 온도의 중앙값을 화면에 보여준다.

상근이는 소프트웨어를 기계에 올리기 전에 컴퓨터에서 테스트해보려고 한다.

총 N초 동안 측정한 온도가 주어졌을 때, 디스플레이에 표시된 중앙값의 합을 구하는 프로그램을 작성하시오. 즉, N개의 수가 주어졌을 때, 길이가 K인 연속 부분 수열 N-K+1개의 중앙값의 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 250,000, 1 ≤ K ≤ 5,000, K ≤ N)

둘째 줄부터 N개 줄에 측정한 온도가 순서대로 주어진다. 온도는 0보다 크거나 같고, 65535보다 작거나 같은 정수이다.

출력

길이가 K인 모든 연속 부분 수열의 중앙값의 합을 출력한다.

예제 입력 1

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

예제 출력 1

60

힌트

수 K개의 중앙값은 ((K+1)/2)번째로 작은 숫자이다. 인덱싱은 1번 부터 시작하며, K가 홀수인 경우를 처리하기 위해 1을 더한다.

예를 들어, (1, 2, 6, 5, 4, 3)의 중앙값은 3이고, (11, 13, 12, 14, 15)의 중앙값은 13이다. 

알고리즘 분류

• 자료 구조

풀이

이 문제와 비슷한 문제다.

1572번: 중앙값

세그먼트 트리를 이용하여 0번째 수부터 K-1개의 수에 대한 정보를 업데이트한다. 세그먼트 트리의 각 노드에는 노드가 담당하는 구간에 속해 있는 수의 개수가 들어있다.

이제 K번째 수부터 하나씩 세그먼트 트리에 업데이트하고, 중앙값, 즉 힌트에서 보았듯이 (K+1)/2번째로 작은 수를 찾는다. 현재 노드에서, 왼쪽 자식 노드에 들어있는 수(왼쪽 자식 노드가 맡고 있는 구간에 속해 있는 수의 개수)가 (K+1)/2 이상이면, (K+1)/2는 왼쪽 자식에 속해있다는 뜻이므로 재귀를 이용하여 왼쪽 자식을 탐색하고, 반대로 (K+1)/2가 더 크다면 오른쪽 자식에 있다는 뜻이므로, 오른쪽 자식을 탐색해준다. 이 때 (K+1)/2에서 왼쪽 자식 노드에 들어있는 수를 빼준다. 현재 노드에서, 작은 순서대로 왼쪽 자식 노드에 들어있는 수만큼이 왼쪽 자식 노드가 맡고 있는 구간에 속해 있고, 현재 노드에 들어 있는 수에서 왼쪽 자식 노드에 들어있는 수를 뺀 개수만큼 오른쪽 자식 노드가 맡고 있는 구간에 속해 있기 때문이다. 이제 중앙값을 찾았으면, 0번째 수를 제거한다.

이렇게 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_N 250001
#define MAX_T 1000001
#define LL long long
#define INF 1e9

using namespace std;
int N, K;
int MAP[MAX_N];
int SegTree[MAX_T];
LL answer = 0;

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

void Update_SegTree(int Node, int S, int E, int Val, int Diff) {
	if (S == E) {
		SegTree[Node] += Diff;
		return;
	}
	int M = (S + E) / 2;
	if (Val <= M) {
		Update_SegTree(Node * 2, S, M, Val, Diff);
	}
	else {
		Update_SegTree(Node * 2 + 1, M + 1, E, Val, Diff);
	}
	SegTree[Node] = SegTree[Node * 2] + SegTree[Node * 2 + 1];
}

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

void Settings() {
	for (int i = 0; i < (K - 1); i++) {
		Update_SegTree(1, 0, 65535, MAP[i], 1);
	}
}

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

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

	return 0;
}