[c++] 백준 - 달리기 (인덱스드 트리)

1. 문제

2. 입출력

3. 예제 입출력

4. 문제 해설

처음에 이 문제를 읽었을 때는 왜 플래티넘 4인가 했다. 단순히 자신보다 앞에 있는 수 중 자신보다 큰 수의 숫자를 구하면 되는 것이 아닌가?라는 생각이 들었다. 

 

그런데 문제 조건을 확인하니 선수의 수 N은 최대가 500000이고 만약 위의 방법을 적용하면 대략 O(N^2)의 시간복잡도를 갖게 된다. 500000 * 5000000 = 25000000000000 = 20조의 연산 횟수가 늘어나고 만약 break문을 통해 중간중간 가지치기를 해준다해도 시간 제한이 1초라는 것은 대략 1억번의 연산안에 결과가 나와야하는 것인데 O(N^2)알고리즘으로는 불가능하다는 생각이 들었다. 

 

가능한 시간 복잡도는 O(NlogN)정도였다. 결국 알고리즘 분류를 봐버렸고 이 문제가 세그먼트 트리 문제로 분류되어 있는 것을 확인할 수 있었다. 또한 앞선 포스팅에서 말했듯이 모든 세그먼트 트리 문제는 인덱스드 트리 문제로 변형해서 풀 수 있기 때문에 나는 인덱스드 트리를 구성해 이 문제에 접근해보고자 했다. 

 

접근 방법

우선 인덱스드 트리는 구간 별 대표값을 이용하는 자료구조이다. 이 문제에서 구간별이라고 함은 자기 자신보다 앞의 구간이라 할 수 있겠다. 우리는 어쨌든 입력 값의 앞에 존재하는 값 중 입력 값보다 큰 수의 개수를 구해야하니 말이다. 

구간 별 대표 값은 처음부터 자기 자신 까지 중 자기보다 큰 수의 개수로 정했다. 

 

이 문제는 사실 예전에 인덱스드 트리를 항상 구성해놓고 풀던 문제들과는 달리 인풋이 들어가는 순서에도 영향을 받는다. 

이미 트리를 들어온 인풋값들로 미리 구성을 해놓으면 우리는 앞에 어떠한 값이 자기 자신보다 큰 지 몇 개인지 알 수 없다. 하지만 내림차순으로 정렬을 한 후라면 알 수 있다! 정렬을 한 후 차례대로 입력을 집어넣는다면 현재 인덱스드 트리 안에 존재하는 수 중 처음부터 자신의 위치까지 존재하는 수의 합이 정답이 되기 때문이다. 그림으로 설명하면 다음과 같다. 

 

예제를 예시로 설명하면 다음과 같다. 

 

위와 같이 정렬된 달리기 실력을 바탕으로 해당 인덱스에 넣어가며 인덱스드 트리의 query함수(처음부터 자기 자신)를 수행해주면 답이 나온다. 물론 정답 배열에 다시 넣어주는 과정은 필요하다!

 

5. 코드 및 해설

#pragma warning (disable:4996)

/*
	첫 번째 방법
	1. mergeSort merge Sort를 진행할 때 순서가 변하는 상황을 추월이라고 생각한다. 
	
	2. 구간 합 문제 
	O(N^2) -> O(logN)으로 만들어 줄 자료구조가 필요하다. 
	! segmentTree
	자신의 리프노드 두 개의 합을 올린다. 
	자식은 최대 두 개 

	segmet Tree의 장점은 구현이 쉽다..?

	인덱스드 트리 
	인덱싱을 한 트리 
	구간 합을 구해 놓는다. 

	-- 2^n만큼의 공간이 필요하다. 
	-- 2^nn >= N*2인 최초의 수 
*/
#include <cstdio>
#include <algorithm>
#define OFFSET 524288
#define SIZE_TR 1048576
using namespace std;
int N; // 선수 수
int Tree[SIZE_TR];
int ans[500004];
struct player {
	int idx;
	int speed;
}; // 원래의 인덱스와 speed를 저장할 구조체
player origin[500004]; // 원본 배열
bool compare (player a, player b) {
	if (a.speed > b.speed) return true;
	else return false;
}
void input() {
	scanf("%d" , &N);

	for (int i = 0; i < N; i++) {
		scanf("%d", &origin[i].speed);
		origin[i].idx = i;
	}
}
void update(int idx) {
	idx += OFFSET;
	Tree[idx] = 1; // 1을 더해준다. 
	while (idx > 0) {
		idx /= 2;
		Tree[idx] = Tree[idx * 2] + Tree[idx * 2 + 1]; // 끝까지 가면서 업데이트
	}
}
int query(int start, int end) {
	int ans = 0;
	start += OFFSET, end += OFFSET; //시작점과 끝점 모두 OFFSET을 더해준다.
	while (start <= end) {
		if (start % 2) ans += Tree[start++];
		if (end % 2 == 0) ans += Tree[end--];
		start /= 2; end /= 2;
	}
	return ans;
}
void sol() {
	sort(origin, origin + N, compare);
	for (int i = 0; i < N; i++) {
		//printf("origin[%d].idx : %d\n", i, origin[i].idx);
		update(origin[i].idx);
		ans[origin[i].idx] = query(0, origin[i].idx);
		//printf("%d\n", query(0, origin[i].idx));
	}

	for (int i = 0; i < N; i++) {
		printf("%d\n", ans[i]);
	}
}
int main() {
	input();
	sol();
	return 0;
}