c언어 2517번 달리기 (백준)

#include <stdio.h>
#include <stdlib.h>

typedef struct A{int x,y;}A; //x index, y power (입력값을 저장할 구조체)
int tree[2000000] = {}; //segment tree (n의 최댓값 50만 * 4)

int compare(const void *a, const void *b) { //qsort, 오름차순 정렬, 구조체 y값 기준
	return (*(A*)a).y - (*(A*)b).y;//왼쪽이 더 크면 +, 오른쪽이 더 크면 -, 같다면 0
}

int find(int s, int e, int node, int l, int r) { //segment tree 탐색
	if(s > r || e < l) return 0;
	if(l <= s && e <= r) return tree[node];
	int m = (s+e)/2;
	return find(s, m, node*2, l, r) + find(m+1, e, node*2+1, l, r);
}

void update(int s, int e, int node, int index, int dif) { //segment tree 갱신
	if(index < s || index > e) return;
	tree[node] += dif;
	if(s==e) return;
	int mid = (s+e)/2;
	update(s, mid, node*2, index, dif);
	update(mid+1, e, node*2+1, index, dif);
}

int main(void) {
	int n;
	scanf("%d",&n); //n입력
	A power[n];
	int ans[n];
	
	for(int i=0; i<n; i++) { //입력 받기
		power[i].x = i; //입력된 순서
		scanf("%d", &power[i].y); //실력
	}

	qsort(power, n, sizeof(A), compare); //오름차순 정렬
	
	for(int i=n-1; i>=0; i--) { //실력이 가장 큰 것부터 작은 순으로
    	//출력할 때는 처음 입력받았던 데로 출력해야 하므로, 그 정보를 담고있는 power[i].x을 이용해서 출력값을 담을 배열의 index로 사용한다.
		ans[power[i].x] = find(0, n-1, 1, 0, power[i].x)+1; //입력된 순서를 범위로 하여 탐색, 자신보다 앞에 있으며 더 실력이 큰 선수들의 수에 1을 더한 값을 출력을 위한 배열에 대입한다.(+1을 하는 이유는 가장 빠른것이 0이 아닌 1이기 때문)
		update(0,n-1,1,power[i].x,1); //갱신 : power[i].x는 처음에 입력받은 순서를 뜻하며, 이 때 입력받은 선수가 완주했음을 의미한다.
	}
	
	for(int i=0; i<n; i++) printf("%d\n",ans[i]); //출력
}

 

풀이 : 세그먼트 트리, 정렬

 

평소 실력이 각각 2, 8, 10, 7, 1, 9, 4, 15라고 하면 각 선수가 얻을 수 있는 최선의 등수는 (같은 순서로) 각각 1, 1, 1, 3, 5, 2, 5, 1이 된다.

 

즉 어떤 선수의 실력보다 더 큰 실력을 가진 선수가 왼쪽(먼저 입력된)에 몇명있는가를 물어보는 문제이다.

위에서 7의 경우 7보다 실력이 크며, 왼쪽에 있는 선수의 수는 8, 10 으로 2명이다 그러므로 (0등이 아닌 1등이 가장 빠른 등수이므로) 2+1, 순위는 3등이 된다.

 

0. segment tree의 크기는 50만 * 4 = 200만으로 잡습니다.

이유 : 실력의 범위는 50만보다 크므로, 실력을 기준으로 segment tree을 만들면 너무 커서 시간이 오래 걸린다.

그 대신 실력으로 정렬을 한다음  입력받은 순서를 이용하여 segment tree을 구성하면 시간을 줄일 수 있다.

최대 50만개의 선수들의 실력을 입력 받기 때문에 크기를 200만으로 잡았다.

 

1. 입력을 받을 때, 입력을 받은 순서와 그 실력을 하나로 묶어서 저장한다 (ex 구조체, 배열, c++ 의 경우 벡터나, pair)

 

2. 1.의 데이터들을 실력을 기준으로 오름차순 (내림차순으로 해도 상관 없긴 합니다)으로 정렬합니다.

 

3. 정렬된 데이터에서, 실력이 큰 순서부터 segment tree을 활용합니다.

이유 : 큰 것 부터 해야 자신의 앞에 자신의 실력보다 더 큰것이 몇 개 인지를 알 수 있습니다.

 

3-1. 처음 입력된 순서부터 자신의 순서까지 자신보다 실력이 큰 것을 확인합니다. 그리고 이 값을 출력을 위한 배열에 저장해 줍니다. (처음 입력받은 순서를 index로 활용합니다.)

무조건 자신보다 실력이 큰 것만 있다는 것을 확신하는 이유 : 실력이 큰 순서부터 segment tree를 진행하고 있기 때문입니다!!!!

 

3-2. segment tree를 갱신해줍니다! 입력받은 순서를 index로 하고 관련된 노드들의 값들을 1 증가시켜주면 됩니다.

 

4. 3-1에서 대입한 값을 1.에서 입력받은 순서대로 출력해주면 됩니다.