[G2] 백준 32510번 키가 비슷한 친구 C++ 세그먼트 트리

리뷰

 

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

세그먼트 트리를 활용하여 풀긴 했는데 시간을 보니 이게 최적해는 절대 아닌듯 하다.

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• t : 테스트 케이스의 개수를 저장할 변수
• n : 사람의 수를 저장할 변수
• k : 키의 범위를 저장할 변수
• tree : 세그먼트 트리 정보를 저장할 배열

 

함수

1. update

void update(int node, int s, int e, int idx, int val) {
	if (s == e) tree[node] = min(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] = min(tree[node * 2], tree[node * 2 + 1]);
	}
}

 

세그먼트 트리 업데이트를 수행할 함수

 

2. query

int query(int node, int s, int e, int L, int R) {
	if (R < s || e < L) return 2e9;
	if (L <= s && e <= R) return tree[node];
	int mid = (s + e) / 2;
	return min(query(node * 2, s, mid, L, R), query(node * 2 + 1, mid + 1, e, L, R));
}

 

세그먼트 트리를 탐색하며 구간 최소값을 구하기 위한 함수

 

 

문제풀이

1. t값을 입력 받고, t번의 테스트케이스를 수행한다.
2. 매 테스트 케이스마다 변수 ans를 0으로 초기화 하고, n, k값을 입력 받은 뒤 tree를 매우 큰 값으로 채운다.
3. n명의 사람을 순회하며 변수 v에 각 사람의 키를 저장한다.
4. update함수를 통해 세그먼트 트리의 v번째 리프 노드에 저장된 값과 i를 비교해 더 작은 값으로 업데이트한다.
5. 변수 res에 query함수를 통해 v-k~v범위의 최소값을 구해 저장한다.
6. ans에 i-res를 더해준다.
7. 탐색이 종료된 후 "Case #" + c + 개행 + ans + 개행을 출력한다.

 

트러블 슈팅

없음

 

 

참고 사항

1. 사람의 키의 범위가 최대 50만이라 최소값 세그먼트 트리를 통한 풀이를 생각했다.
2. 알고리즘 분류를 보니 정렬과 우선순위 큐를 통한 그리디한 더 좋은 최적해가 있는 듯 하다.

 

정답 코드

#include<iostream>
#include<cstring>
using namespace std;
using ll = long long;

const int N = 5e5 + 1;
int t, n, k;
int tree[N * 4];

void update(int node, int s, int e, int idx, int val) {
	if (s == e) tree[node] = min(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] = min(tree[node * 2], tree[node * 2 + 1]);
	}
}

int query(int node, int s, int e, int L, int R) {
	if (R < s || e < L) return 2e9;
	if (L <= s && e <= R) return tree[node];
	int mid = (s + e) / 2;
	return min(query(node * 2, s, mid, L, R), query(node * 2 + 1, mid + 1, e, L, R));
}

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

	cin >> t;
	for (int c = 1; c <= t; ++c) {
		ll ans = 0;
		cin >> n >> k;
		fill(tree, tree + N * 4, 2e9);

		for (int i = 0; i < n; ++i) {
			int v; cin >> v;
			update(1, 0, 5e5, v, i);
			int res = query(1, 0, 5e5, v - k, v);
			ans += i - res;
		}

		cout << "Case #" << c << "\n" << ans << "\n";
	}
}