c언어 1517번 버블 소트 (백준)

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

typedef struct A{int x,y; /*x (index) y (value)*/}A;
int tree[2000000] = {};

int compare(const void *a, const void *b) { //value 기준 오름차순 정렬 
	return (*(A*)a).y - (*(A*)b).y;
}

int update(int s, int e, int node, int index) {
	if(s>index || e<index) return tree[node];
	if(s==e) return tree[node] = 1;
	int m = (s+e)/2;
	return tree[node] = update(s,m,node*2,index) + update(m+1,e,node*2+1,index);
}

int find(int s, int e, int node, int l, int r) {
	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);
}

int main(void) {
	int n,m;
	long long ans = 0;
	scanf("%d",&n);
	
	A arr[n];
	for(int i=0; i<n; i++) {
		scanf("%d",&m);
		arr[i].x = i;
		arr[i].y = m;
	}
	
	qsort(arr, n, sizeof(A), compare);
	
	for(int i=n-1; i>=0; i--) {
		ans += find(0,n-1,1,0,arr[i].x-1);
		update(0,n-1,1,arr[i].x);
	} printf("%lld",ans);
}

 

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

 

0. 세그먼트 트리를 준비합니다. 특정 index의 값을 1씩 늘리는 update와 구간합을 가져오는 find을 준비합니다.

1. 입력을 언제 받았는가 (x) 입력값이 무엇인가(y)을 한묶음으로 저장합니다.

2.  y를 기준으로 오름차순 정렬을 합니다 (위의 데이터를)

 

3. y값이 큰 데이터부터 순차적으로 (내림차순) 다룹니다.

3.1 특정 y값이 입력되기 전에 더 큰 숫자들의 개수를 구합니다. 그리고 이것을 ans에 누적합니다.

3.2 그다음, y값이 입력이 되었던 순서를(x값) index로 하여 세그먼트 트리에 update을 해줍니다 (관련된 노드의 값이 1씩 증가하게 됩니다)

 

핵심은 정렬을 한 후 큰 숫자(y값)부터 다루며, 이 숫자가 입력되기 전에(x값) 이보다 더 큰 수가 몇 개 있는지를 확인(find)하고 ( 큰 수의 개수가 swap을 해야할 횟수와 같습니다) 다음에 더 작은 수를 위해서 세그먼트 트리에 x번째에 큰 수 가 있다는 것을 update해줍니다. 이 과정을 반복하면 전체 swap 횟수를 구할 수 있습니다!!!!

 

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