[ BOJ ] 1517 : 버블 소트 ( PLATINUM 5 ) / C

문제

N개의 수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에 대해서 버블 소트를 수행할 때, Swap이 총 몇 번 발생하는지 알아내는 프로그램을 작성하시오.

버블 소트는 서로 인접해 있는 두 수를 바꿔가며 정렬하는 방법이다. 예를 들어 수열이 3 2 1 이었다고 하자. 이 경우에는 인접해 있는 3, 2가 바뀌어야 하므로 2 3 1 이 된다. 다음으로는 3, 1이 바뀌어야 하므로 2 1 3 이 된다. 다음에는 2, 1이 바뀌어야 하므로 1 2 3 이 된다. 그러면 더 이상 바꿔야 할 경우가 없으므로 정렬이 완료된다.

입력

첫째 줄에 N(1 ≤ N ≤ 500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0 ≤ |A[i]| ≤ 1,000,000,000의 범위에 들어있다.

출력

첫째 줄에 Swap 횟수를 출력한다.

풀이 과정

1. 입력된 수들을 Merge Sort 를 이용해 정렬한 후, 중복을 없애고 좌표 압축을 진행한다.

2. 압축한 좌표를 이분 탐색으로 찾아 세그먼트 트리를 이용해 inversion counting을 진행한다.

#include <stdio.h>
#define SIZE 500001
typedef long long LL;

LL arr[SIZE];
LL tarr[SIZE];
LL darr[SIZE];
int darrLen = 0;

LL marr[SIZE];

LL tree[SIZE * 4] = {0,};

void update(int start, int end, int idx, int what) {
	if (what < start || end < what) return;
	if (start == end) {
		tree[idx] += 1;
		return; 
	}

	int mid = (start + end) / 2;
	update(start, mid, idx * 2, what);
	update(mid + 1, end, idx * 2 + 1, what);
	tree[idx] = tree[idx * 2] + tree[idx * 2 + 1];
}

LL interval_sum(int start, int end, int idx, int left, int right) {
	if (end < left || right < start) return 0;
	if (left <= start && end <= right) return tree[idx];

	int mid = (start + end) / 2;
	return interval_sum(start, mid, idx * 2, left, right) + interval_sum(mid + 1, end, idx * 2 + 1, left, right);
}

void merge(LL now[], int start, int mid, int end) {
	int leftidx = start;
	int rightidx = mid + 1;
	int allidx = start;

	while(leftidx <= mid && rightidx <= end) {
		if(now[leftidx] < now[rightidx])
			marr[allidx++] = now[leftidx++];
		else
			marr[allidx++] = now[rightidx++];
	}

	while(leftidx <= mid) {
		marr[allidx++] = now[leftidx++];
	}
	while(rightidx <= end) {
		marr[allidx++] = now[rightidx++];
	}

	for(int i = start; i <= end; i++) {
		now[i] = marr[i];
	}
}

void merge_sort(LL now[], int start, int end) {
	if(start >= end) return;
	int mid = (start + end) / 2;
	merge_sort(now, start, mid);
	merge_sort(now, mid + 1, end);
	merge(now, start, mid, end);
}

int binary_search(int start, int end, int key) {
	if(start == end) return start;

	int mid = (start + end) / 2;
	if(darr[mid] == key) return mid;
	else if(darr[mid] > key) return binary_search(start, mid, key);
	else return binary_search(mid + 1, end, key);
}

int main(void) {
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%lld", &arr[i]);
		tarr[i] = arr[i];
	}
	merge_sort(tarr, 0, n - 1);
	darr[darrLen++] = tarr[0];
	for (int i = 1; i < n; i++) {
		if(darr[darrLen - 1] != tarr[i]) {
			darr[darrLen++] = tarr[i];
		}
	}

	LL result = 0;
	for (int i = 0; i < n; i++) {
		int idx = binary_search(0, darrLen - 1, arr[i]);
		update(0, darrLen - 1, 1, idx);
		if (idx != darrLen - 1) result += interval_sum(0, darrLen - 1, 1, idx + 1, darrLen - 1);
	}

	printf("%lld", result);
	return 0;
}

inversion counting 에 대한 설명 : https://jonyo.tistory.com/99

[알고리즘] Inversion Count (Merge Sort)