백준 / 1517 버블 소트 C++

www.acmicpc.net/problem/1517

1517번: 버블 소트

처음 생각했던 것은 O(nlogn) 정렬을 활용해 정렬 후 기존 배열의 인덱스를 비교해가며 더하는 것이었는데 배열에 중복된 값이 존재하면 안 된다는 것을 깨달았습니다.

아이디어가 떠오르지 않아 다른 분들의 풀이를 참고했습니다.

 

아이디어 : merge sort 과정에서 교차점의 개수와 버블 소트의 swap 횟수는 같다.

예를 들어 1 3 5 7 / 2 4 6 8 을 정렬한다고 하면 swap 횟수는 6번이고 merge 과정이 아래와 같습니다.  

교차점의 개수도 총 6개임을 알 수 있습니다. 

이 둘의 값이 동일한 이유는 (오름차순)버블 소트가 오른쪽의 값과 비교하여 크면 swap하는 원리이기 때문입니다. swap 과정이 위의 merge 과정에서의 교차지점과 동일하기 때문입니다.

(7의 경우 2,4,6 과 swap을 해야하고, 해당 교차점은 3개)

(좀 더 찾아보니 Inversion Counting 이라는 기법이 이에 해당합니다.)

 

 그러므로 왼쪽이나 오른쪽 하나를 기준으로 merge 과정에서 교차점의 개수를 구해주면 됩니다.

 

코드는 다음과 같습니다.

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>

using namespace std;

int n;
int arr[500001];
int tmp[500001];
long long result = 0;

void init()
{
	cin >> n;
	for (int i = 0; i < n; i++) {
		int num;
		cin >> num;
		arr[i] = num;
	}
}

// 버블 소트의 swap 개수 
// = merge 소트에서 merge과정에서의 교차점 개수
// 오름차순 정렬 기준으로
// 왼쪽 배열의 값이 tmp에 정렬될 때마다 cnt 더해줌
// 오른쪽 배열의 값이 tmp에 정렬될 때마다 cnt+1
// (오른쪽 배열의 값이 정렬된다는 것은 해당 값 이전의 오른쪽 배열 값은
// 이미 정렬된 상황이므로 교차점이 이전 오른쪽 배열의 값에 +1 한 것과 같음)

// 합병, 교차점도 함께 구하기
void merge(int start, int last)
{
	int mid = (start + last) / 2;
	int i = start;
	int j = mid + 1;
	int k = start;
	int cnt = 0;

	while (i <= mid && j <= last) {
		// 왼쪽 배열의 값이 정렬될 때
		if (arr[i] <= arr[j]) {
			tmp[k++] = arr[i++];
			result += (long long)cnt;
		}
		// 오른쪽 배열의 값이 정렬될 때
		else {
			tmp[k++] = arr[j++];
			cnt++;
		}
	}

	// 남은 부분 중 오른쪽 배열의 값이 정렬될 때
	if (i > mid) {
		int s = j;
		while (s <= last) {
			tmp[k++] = arr[s++];
			cnt++;
		}
	}
	// 남은 부분 중 왼쪽 배열의 값이 정렬될 때
	else {
		int s = i;
		while (s <= mid) {
			tmp[k++] = arr[s++];
			result += (long long)cnt;
		}
	}

	for (int t = start; t <= last; t++)
		arr[t] = tmp[t];
}

void mergesort(int start, int last)
{
	if (start < last) {
		int mid = (start + last) / 2;
		mergesort(start, mid);
		mergesort(mid + 1, last);
		merge(start, last);
	}
}

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

	init();
	mergesort(0, n - 1);
	cout << result;
}