[백준] 1517번 - 버블 소트 (C언어) [Platinum5]

input	output
3 3 2 1	3

해당 문제는 버블 정렬에 대한 개념을 설명하고 SWAP이 일어나는 횟수를 구하는 문제여서 단순히 버블정렬을 사용한다면 시간초과가 발생한다. 시간 제한이 1초이므로 시간복잡도가 O(N^2)인 버블정렬로는 절대 구현할 수 없다. 보다 빠른 알고리즘인 합병정렬을 사용하거나 세그먼트 트리를 이용하면 O(NlogN)의 시간 복잡도를 가지므로 문제 해결이 가능하다. 

 

필자는 합병 정렬을 사용하였다. 

우선, 버블 정렬에서 SWAP이 일어나는 구간은 어떤 원소 i가 존재할 때, i보다 앞에 있으면서 작은 수들을 뒤로 보낼때 작은 수들의 갯수만큼 SWAP이 일어난다. 따라서 합병 정렬에서는 정복 단계에서 SWAP이 일어나고 정렬은 합병 단계에서 일어난다. 버블 정렬에서 SWAP의 경우와 유사한 경우를 합병정렬에서 찾아보면 오른쪽으로 분할된 리스트의 원소가 왼쪽으로 분할된 리스트의 원소보다 작은 경우 SWAP이 일어나고 각 리스트의 인덱스간의 차이를 저장하여 더 하면 SWAP 횟수를 구할 수 있다. 

 

전체 소스 코드는 아래와 같다.

#include <stdio.h>
#pragma warning(disable:4996)
typedef long long int ll;

ll sorted[500001];
ll arr[500001];
ll answer = 0;

void merge(int left, int mid, int right) {
	int i = left;
	int j = mid + 1;
	int k = left;

	while (i <= mid && j <= right) {
		if (arr[i] <= arr[j]) {
			sorted[k] = arr[i];
			i++;
		}
		else {
			sorted[k] = arr[j];
			answer += j - k; // swap 구간
			j++;
		}
		k++;
	}

	if (i > mid) {
		for (int a = j; a <= right;a++) {
			sorted[k++] = arr[a];
		}
	}
	else {
		for (int a = i; a <= mid; a++) {
			sorted[k++] = arr[a];
		}
	}

	for (int a = left; a <= right;a++) {
		arr[a] = sorted[a];
	}
}

void merge_sort(int left, int right) {
	if (left >= right) return;
	int mid = (left + right) / 2;
	merge_sort(left, mid);
	merge_sort(mid + 1, right);
	merge(left, mid, right);
}

int main() {
	int n;
	scanf("%d", &n);

	for (int i = 0; i < n;i++)
		scanf("%lld", &arr[i]);

	merge_sort(0, n - 1);
	printf("%lld", answer);

	return 0;
}

해당 문제는 합병 정렬에 대한 지식이 충분하다면 쉽게 해결 가능한 문제이다. 다음엔 세그먼트 트리로 도전할 것이다.

 

[1517번]

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

1517번: 버블 소트

 

[github]

https://github.com/MinWook6457

MinWook6457 - Overview