[P5] 백준 1572번 중앙값, 9426번 중앙값 측정 C++ 세그먼트 트리, 슬라이딩 윈도우

리뷰

 

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

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

처음엔 머지 소트 트리를 통해 접근하였으나 바로 시간 초과를 맞게 되었다.

이후 도는 0보다 크거나 같고, 65535보다 작거나 같은 정수라는 조건에 영감을 얻어 구간합 세그트리로 AC를 받았다.

1572번과 9426번 둘 다 같은 문제로 9426번은 레이팅 점수를 주지 않는다.

 

 

전역 변수

• N : n의 최대값을 저장할 정수형 상수 변수
• P : 온도의 최대값을 저장할 정수형 상수 변수
• n : 수열의 길이를 저장할 정수형 변수
• k : 부분 수열의 길이를 저장할 정수형 변수
• lst : 수열의 값을 저장할 정수형 배열
• tree : 세그먼트 트리 정보를 저장할 정수형 배열

 

함수

1. update

void update(int node, int s, int e, int idx, int val)

 

세그먼트 트리의 업데이트를 진행하기 위한 함수

1. 매개변수로 노드 정보 node, 탐색 범위 s, e, 변경할 인덱스 idx, 변경할 값 val을 전달받는다.
2. 기저 조건으로 리프 노드에 도달했을 경우 현재 노드에 val만큼 값을 더해준다.
3. 리프 노드가 아닐 경우 정수형 변수 mid에 탐색 범위의 절반 값을 저장한다.
4. idx가 mid보다 작거나 같을 경우 왼쪽 자식 노드로, 클 경우 오른쪽 자식 노드로 재귀를 진행한다.
5. 재귀를 빠져나오며 현재 노드를 좌, 우 자식 노드 값의 합으로 저장하여 트리 상태를 업데이트 해준다.

 

2. query

int query(int node, int s, int e, int idx)

 

현재 부분 수열에서 중앙값을 찾아 리턴하기 위한 함수

1. 기저조건으로 리프 노드에 도달하였다면 s, e 중 아무거나 리턴해 준다.
2. 리프 노드가 아닐 경우 정수형 변수 mid에 탐색 범위의 절반 값을 저장한다.
3. idx가 왼쪽 자식 노드의 값 보다 작거나 같을 경우 왼쪽으로 재귀를 진행해 준다.
4. idx가 왼쪽 자식 노드의 값 보다 크다면 오른쪽으로 재귀를 진행해 준다.

 

문제풀이

1. n, k값을 입력 받고, n개의 수열의 요소를 입력 받아 lst배열에 저장해 준다.
2. 초기 k개의 원소를 update함수를 통해 세그먼트 트리 업데이트를 진행해 준다.
3. 초기 ans의 값을 query함수를 통해 세그먼트 트리에서 (k + 1) / 2번째 큰 값으로 초기화 해준다.
4. 다시 k부터 n - 1까지 인덱스를 가지는 for문을 개행해 준다.
5. update 함수를 통해 이전의 요소의 값을 -1만큼 더해 제거해 준다.
6. update 함수를 통해 현재 요소의 값을 1만큼 더해 추가해 준다.
7. query 함수를 통해 업데이트 된 세그먼트 트리에서 (k + 1) / 2번째 큰 값을 구해 ans에 더해준다.
8. 모든 탐색을 마친 후에 ans에 저장된 값을 출력해 준다.

 

트러블 슈팅

1. 머지 소트 트리를 구현하고, 중앙 값을 구해 ans에 더해주는 식의 풀이를 진행했으나 시간 초과를 받았다.
2. ans의 값을 int로 설정한 상태로 제출하였다가 Fail을 받았다.
3. 최악의 경우 수열의 모든 원소가 65534일 경우 int 오버플로우가 발생함을 깨달았다.
4. ans를 long long타입으로 변환 후 제출하여 AC를 받았다.

 

참고 사항

• 수열 내에 중복된 값이 존재할 수 있으니 업데이트 시 0, 1로 변경이 아닌 1씩 더하거나 빼주어야 한다.

 

정답 코드

#include<iostream>
using namespace std;

const int N = 250000;
const int P = 65535;
int n, k;
int lst[N];
int tree[P * 4];

void update(int node, int s, int e, int idx, int val) {
	if (s == e) tree[node] += val;
	else {
		int mid = (s + e) / 2;
		if (idx <= mid) update(node * 2, s, mid, idx, val);
		else update(node * 2 + 1, mid + 1, e, idx, val);
		tree[node] = tree[node * 2] + tree[node * 2 + 1];
	}
}

int query(int node, int s, int e, int idx) {
	if (s == e) return s;
	int mid = (s + e) / 2;
	if (idx <= tree[node * 2]) return query(node * 2, s, mid, idx);
	else return query(node * 2 + 1, mid + 1, e, idx - tree[node * 2]);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> k;
	for (int i = 0; i < n; ++i) cin >> lst[i];
	for (int i = 0; i < k; ++i) {
		update(1, 0, P, lst[i], 1);
	}

	long long ans = query(1, 0, P, (k + 1) / 2);
	for (int i = k; i < n; ++i) {
		update(1, 0, P, lst[i - k], -1);
		update(1, 0, P, lst[i], 1);
		ans += query(1, 0, P, (k + 1) / 2);
	}
	cout << ans;
}