[C/C++] 백준 1517번 - 버블 소트

✏️ 문제 링크

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

1517번: 버블 소트

 

✏️ 문제 설명

✏️ 문제 풀이

  제목은 버블 정렬이지만 버블 정렬로 풀면 N<=500,000 이므로 시간 초과가 발생합니다.

  따라서 시간 복잡도가 O(nlogn)인 병합 정렬로 접근해야 합니다.

  기본적인 병합 정렬과 비슷하나 중간에 swap해주는 개수를 count해줘서 result로 출력해야함

  그룹들을 병합할 때 앞 그룹과 뒤 그룹의 데이터 값을 비교하면서 배열의 인덱스를 채워주는데,

  여기서 뒤 그룹의 데이터가 더 작아서 배열의 앞쪽에 채우게 되는 경우에는 swap이 발생한다고 생각하면 됩니다.

 

✏️ 문제 코드

#include<iostream>
#include<vector>
using namespace std;

static vector<int>A;
vector<int>temp;
void merge_sort(int start, int end);
static long result;

int main() {

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

	int N;
	cin >> N;

	A = vector<int>(N + 1, 0);
	temp = vector<int>(N + 1, 0);

	for (int i = 1; i <= N; i++)
		cin >> A[i];
	result = 0;
	merge_sort(1, N);
	cout << result;
}
void merge_sort(int start, int end) {

	if (end - start < 1)
		return;

	int middle = start + (end - start) / 2;

	merge_sort(start, middle);
	merge_sort(middle + 1, end);

	for (int i = start; i <= end; i++)
		temp[i] = A[i];

	int index1 = start;
	int k = start;
	int index2 = middle+1;

	while (index1 <= middle && index2 <= end) {
		if (temp[index1] > temp[index2]) {
			A[k] = temp[index2];
			result = result + index2 - k;
			index2++;
			k++;
		}
		else {
			A[k] = temp[index1];
			index1++;
			k++;
		}
	}

	while (index1 <= middle) {
		A[k] = temp[index1];
		k++;
		index1++;
	}
	while (index2 <= end) {
		A[k] = temp[index2];
		k++;
		index2++;
	}
}