(c++)백준 1517번: 버블 소트

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

1517번: 버블 소트

[풀이]

버블소트 문제지만 버블소트로 풀면 시간초과가 나온다. (시간복잡도O(n^2))

그래서 시간복잡도가 O(nlogn)인 mergesort를 사용하여 풀었다.

버블 소트 swap은 인접해 있는 두 수를 바꾸는 것이므로, merge를 할 때 두 수의 앞뒤 순서가 바뀌면 두 수의 거리를 카운트하는 변수에 더하면 된다. 

 

#include <iostream>
#include <vector>
using namespace std;
#define Max 500000

vector<int> v;
int N;
long long ans = 0;

void merge(int start, int mid, int end, int left, int right) {
	vector<int>temp;
	while (left <= mid && right <= end) {
		if (v[left] <= v[right]) {
			temp.push_back(v[left++]);
		}
		//앞뒤 순서를 바꿔야 하는 상황이면 두 수가 떨어진 거리만큼 ans에 더하기
		else {
			temp.push_back(v[right++]);
			ans += (mid + 1 - left);
		}
	}
	while (left <= mid) {
		temp.push_back(v[left++]);
	}
	while (right <= end) {
		temp.push_back(v[right++]);
	}
	for (int i = start, j = 0; i <= end; i++, j++) {
		v[i] = temp[j];
	}
}

void mergeSort(int start,int end) {
	int mid = (start + end) / 2;
	int l = start;
	int r = mid + 1;

	if (start == end)
		return;

	mergeSort(start, mid);
	mergeSort(mid + 1, end);

	merge(start, mid, end, l, r);
}

int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		int a;
		cin >> a;
		v.push_back(a);
	}
	mergeSort(0, N - 1);
	cout << ans << '\n';
	return 0;
}