[P4] 백준 2517번 달리기 C++ 세그먼트 트리, 값/좌표 압축, 이분 탐색, 오프라인 쿼리

리뷰

 

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

주어지는 값을 인덱스로 압축하여 세그먼트 트리의 노드로 관리하여 누적합을 구하는 문제

 

 

전역 변수

• n : 선수의 수를 저장하기 위한 정수형 변수
• lst : 선수의 평소 실력을 저장하기 위한 정수형 배열
• press : 선수의 실력 정보를 오름차순으로 정렬하기 위한 정수형 배열
• tree : 세그먼트 트리 정보를 저장하기 위한 정수형 배열

 

함수

1. update

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

 

세그먼트 트리 정보를 업데이트 하기 위한 함수

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

 

2. query

int query(int node, int s, int e, int L, int R)

 

현재 선수의 평소 실력보다 크거나 같은 선수의 개수를 구하기 위한 함수

1. 매개 변수로 노드 정보 node, 탐색 범위 s, e, 구하고자 하는 범위 L, R을 전달 받는다.
2. 첫 번째 기저 조건으로 탐색 범위가 구하고자 하는 범위를 벗어난 경우 0을 리턴해 준다.
3. 두 번째 기저 조건으로 탐색 범위가 구하고자 하는 범위와 겹칠 경우 현재 노드의 값을 리턴해 준다.
4. 기저 조건에 해당하지 않을 경우 좌, 우 자식 노드로 재귀를 진행하고 각 값을 left, right로 저장해 준다.
5. left + right값을 리턴해 준다.

 

문제풀이

1. n값을 입력 받고, n명의 선수의 평소 실력 정보를 lst배열에 입력 받아주고, press배열에도 동일하게 받아준다.
2. press배열을 오름차순으로 정렬해 주고, 다시 n번의 for문을 개행해 준다.
3. lower_bound 함수를 통해 press에서 현재 선수의 값의 인덱스를 변수 idx에 저장해 준다.
4. update 함수를 통해 idx에 값을 증가시켜 준다.
5. query 함수를 통해 idx ~ n -1의 누적합을 구해 출력해 준 뒤 줄바꿈을 수행해 준다.

 

트러블 슈팅

1. set을 사용한 문제 풀이를 진행했으나, 시간 초과를 받게 되었다.
2. 각 값의 인덱스를 구해 세그먼트 트리의 노드로 활용하여 AC를 받았다.

 

참고 사항

• 참가한 선수들의 평소 실력은 모두 다르다는 조건이 있으므로 중복을 제거할 필요가 없다.

 

정답 코드

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 500000;
int n;
int lst[N];
int press[N];
int tree[N * 4];

void update(int node, int s, int e, int idx) {
	if (s == e) tree[node]++;
	else {
		int mid = (s + e) / 2;
		if (idx <= mid) update(node * 2, s, mid, idx);
		else update(node * 2 + 1, mid + 1, e, idx);
		tree[node] = 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 0;
	if (L <= s && e <= R) return tree[node];
	int mid = (s + e) / 2;
	int left = query(node * 2, s, mid, L, R);
	int right = query(node * 2 + 1, mid + 1, e, L, R);
	return left + right;
}

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

	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> lst[i];
		press[i] = lst[i];
	}

	sort(press, press + n);
	for (int i = 0; i < n; ++i) {
		int idx = lower_bound(press, press + n, lst[i]) - press;
		update(1, 0, n - 1, idx);
		cout << query(1, 0, n - 1, idx, n - 1) << "\n";
	}
}