Beakjoon] 버블 소트 2 (백준 1517코테) - 정렬

---

문제주소 : https://www.acmicpc.net/problem/1517

1517번: 버블 소트

문제 

 

풀이 

문제 그대로 버블정렬로 카운트는 가능하지만 O(n^2)의 경우 시간복잡도에서 실패하게 된다.
O(nlogn)의 시간복잡도로 문제를 풀어야 하는데
핵심 이론은 병합 정렬을 사용하되 병합정렬 시 뒤쪽 데이터가 앞으로 이동하는 경우는 이동한 칸만큼 swap이 일어났다고 볼 수 있다는 것이다.
(이미 앞쪽데이터는 스왑에 의해 자동으로 뒤로 밀려나기에 카운트에서 빼줘야 한다)

 

코드는 아래 숨김

#include <iostream>
#include <vector>

static std::vector<int> nums_arr;
static std::vector<int> temp_arr;
long long result = 0;


void MergeSort(int start, int end) {
	if (end - start < 1)
		return;

	int pivot = start+ (end-start)/ 2;
	MergeSort(start, pivot);
	MergeSort(pivot + 1, end);

	int index1 = start;
	int index2 = pivot + 1;

	int result_index = start;

	for (int i = start; i <= end; ++i) {
		temp_arr[i] = nums_arr[i];
	}

	while (index1 <= pivot && index2 <= end) {
		if (temp_arr[index1] > temp_arr[index2]) {
			nums_arr[result_index] = temp_arr[index2];
			result = result + index2 - result_index;
			index2++, result_index++;			
		}
		else {
			nums_arr[result_index] = temp_arr[index1];			
			//if (index1 > result_index)
			//	result = result + (index1 - result_index);
			index1++, result_index++;
		}		
	}
	
	
	while (index1 <= pivot) {
		nums_arr[result_index] = temp_arr[index1];		
		//if (index1 > result_index)
		//	result = result + (index1 - result_index);
		index1++, result_index++;
	}

	while (index2 <= end) {
		nums_arr[result_index] = temp_arr[index2];		
		//if (index2 > result_index)
		//	result = result + (index2 - result_index);
		index2++, result_index++;
	}
}


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

	int N;
	std::cin >> N;
	
	nums_arr = std::vector<int>(N+1, 0);
	temp_arr = std::vector<int>(N+1, 0);
	for (int i = 1; i <= N; ++i)
	{
		std::cin >> nums_arr[i];
	}

	MergeSort(1, N);

	std::cout << result;
	return 0;
}

 

알게 된 것

 - 병합 정렬을 사용하되 병합정렬시 뒤쪽 데이터가 앞으로 이동하는 경우는 이동한 칸만큼 swap이 일어났다고 볼 수 있다는 것.
 - 알뜰 살뜰하게 이동한 칸의 수가 int를 초과하는 케이스를 넣어놨다..(n^2으로 가능하므로) 그냥 어지간하면 long long으로 선언하는 게 낫겠다
 - 정렬 들어와서 처음으로 재밌었던 문제

---