백준 1572 c++ "중앙값" -PlusUltraCode-

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

 

[필자 사고]

이 문제는 중앙값 찾기 . 세그먼트 트리를 이용하여 풀었다.

입력값으로 주어지는 숫자가 세그먼트 트리에서 리프노드기준으로 인덱스라고 생각하고 풀면 쉽다.

예를들면 입력값이 6이라고 한다면 왼쪽 리프노드부터 6번째 노드에 +1 을 하면 된다.

그래서 중앙값을 찾고 싶을때는 getMid를 통해 갯수를 확인하면서 원하는 지점에 방문하면 start 즉 해당 인덱스 값 을

ans 에 더하면 문제를 해결할 수 있다.

[코드 해설]

 

• 문제 정의
  • 길이가 N인 배열 arr에서 길이가 K인 구간을 이동하면서, 각 구간의 중간값을 구하고 이를 모두 더한 값을 출력한다.
  • 중간값은 정렬된 구간에서 (K + 1) / 2번째에 위치한 값이다.
• 세그먼트 트리를 이용한 중간값 계산
  • 세그먼트 트리의 역할
    세그먼트 트리는 값의 빈도수를 저장하며, 특정 범위에서 원하는 순위(중간값)를 빠르게 찾을 수 있도록 한다.
  • 트리의 구현
    • tree[node]는 해당 노드가 담당하는 범위의 값들의 빈도 합을 저장한다.
    • 예를 들어, 값 x가 arr에 포함되면 세그먼트 트리에서 x에 해당하는 위치를 업데이트하여 빈도를 증가시킨다.
• 함수 설명
  • 입력으로 받은 count에 해당하는 순위의 값을 찾아 ans에 더한다.
  • start == end인 경우, 해당 값이 중간값이므로 ans에 더한다.
  • tree[node * 2]은 왼쪽 자식 노드의 빈도 합을 나타낸다.
    • 만약 count가 왼쪽 자식 노드의 범위에 속하면 왼쪽으로 탐색(getMid(node * 2, ...)).
    • 그렇지 않으면 오른쪽으로 탐색하며, count에서 왼쪽 노드의 빈도 합을 뺀다(getMid(node * 2 + 1, ...)).
  Update 함수: 값의 빈도 업데이트
  • 배열 값 idx에 대해 빈도를 diff만큼 증가시키거나 감소시킨다.
  • 세그먼트 트리의 모든 관련 노드들을 업데이트하여 빈도 합을 유지한다.
  • 재귀적으로 자식 노드를 방문하며, idx가 속하는 노드를 업데이트한다.
  Game_Start 함수: 메인 로직
  • 배열 arr의 첫 K개 구간에 대해 초기 중간값을 계산하여 ans에 추가한다.
  • 이후 슬라이딩 윈도우 방식으로 구간을 이동하면서:
    • 새로 포함된 값은 Update로 빈도 추가.
    • 제외된 값은 Update로 빈도 감소.
    • getMid를 호출하여 현재 구간의 중간값을 계산하고 ans에 추가.
• getMid 함수: 중간값 찾기
• 메인 함수
  • Game_Start 함수에서 입력을 받고, 모든 구간에 대한 중간값의 합을 계산하여 출력한다.
• 시간 복잡도
  • 세그먼트 트리의 깊이는 O(log M) (여기서 M은 값의 범위, 최대 1,000,000).
  • 각 구간에 대해 업데이트 2회와 중간값 찾기 1회가 이루어지므로, 총 복잡도는 O(N log M).
•  

 

[소스 코드]

#include <iostream>
#include <vector>

using namespace std;

int N, K;
vector<long> tree;
vector<long> arr;
long ans = 0;

void getMid(int node, int start, int end,int count) {
	if (start == end) {
		ans += start;
		return;
	}

	int mid = (start + end) / 2;
	if (tree[node * 2] >= count) {
		getMid(node * 2, start, mid, count);
	}
	else {
		getMid(node * 2 + 1, mid + 1, end, count - tree[node * 2]);
	}
}

void Update(int node, int start, int end, int idx, int diff) {
	if (idx < start || end < idx)return;
	if (start == end) {
		tree[node] += diff;
		return;
	}
	int mid = (start + end) / 2;
	if (mid >= idx) {
		Update(node * 2, start, mid, idx, diff);
	}
	else {
		Update(node * 2 + 1, mid + 1, end, idx, diff);
	}
	tree[node] += diff;

}


void Game_Start() {
	cin >> N >> K;
	tree.resize(1000000 * 4 + 1);
	arr.resize(N + 1);
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}

	for (int i = 0; i <K; i++) {
		Update(1, 0, 1000000, arr[i], 1);
	}

	getMid(1, 0, 1000000, (K+ 1) / 2);
	for (int i = K; i < N; i++) {
		Update(1, 0, 1000000, arr[i], 1);
		Update(1, 0, 1000000, arr[i - K ], -1);
		getMid(1, 0, 1000000, (K + 1) / 2);
	}
	cout << ans;
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	Game_Start();

}