백준 1517번 문제는 "버블 소트"로, 정렬 과정에서 서로 인접한 두 원소를 비교해 가며 순서에 맞지 않는 경우 위치를 바꾸는 방식의 버블 정렬을 사용할 때, 실제로 몇 번이나 위치를 바꿔야 하는지를 구하는 문제입니다. 이 문제는 초등학생도 이해할 수 있도록 매우 쉬운 방식으로 설명하고 접근하는 방법을 설명하겠습니다.
문제 이해하기
상상해 보세요, 여러분이 작은 공들을 일렬로 나열하려고 합니다. 각 공에는 숫자가 적혀 있고, 이 숫자들을 작은 숫자부터 큰 숫자 순서로 나열하려고 합니다. 하지만 공을 옮길 때마다, 옮긴 횟수를 적어야 합니다. 여러분의 목표는 공들을 올바른 순서로 만들면서, 옮긴 횟수도 알아내는 것입니다.
문제의 접근 방법
이 문제를 해결하기 위해서는 버블 정렬 방식을 사용하는 대신, 효율적인 방법을 사용해야 합니다. 왜냐하면 버블 정렬은 매우 느리고, 이 문제에서는 실제 정렬을 실행하는 것보다 몇 번 위치를 바꾸는지만 알면 되기 때문입니다. 여기서 사용할 수 있는 한 가지 방법은 "병합 정렬(Merge Sort)"을 변형하여 사용하는 것입니다.
병합 정렬을 사용하면서, 두 부분으로 나눈 배열을 합칠 때, 오른쪽 배열에서 왼쪽 배열로 원소를 옮기는 경우, 그 원소가 왼쪽 배열의 남아 있는 원소 수만큼 위치를 옮겨야 한다는 사실을 이용합니다. 이렇게 하면 실제로 위치를 바꾸는 횟수를 정확히 계산할 수 있습니다.
정답 코드 (C언어)
아래 코드는 병합 정렬을 이용하여 위치를 바꾸는 횟수를 계산하는 방법을 구현한 것입니다. 이 코드를 그대로 복사하여 사용하시면 됩니다.
#include <stdio.h>
#include <stdlib.h>
long long count = 0;
void merge(int *array, int start, int mid, int end) {
int i = start, j = mid+1, k = 0, temp[end-start+1];
while(i <= mid && j <= end) {
if(array[i] <= array[j]) {
temp[k++] = array[i++];
} else {
temp[k++] = array[j++];
count += mid - i + 1; // 왼쪽 배열의 남은 원소 수만큼 카운트 증가
}
}
while(i <= mid) temp[k++] = array[i++];
while(j <= end) temp[k++] = array[j++];
for(i = start, k = 0; i <= end; i++, k++) array[i] = temp[k];
}
void mergeSort(int *array, int start, int end) {
if(start < end) {
int mid = (start + end) / 2;
mergeSort(array, start, mid);
mergeSort(array, mid+1, end);
merge(array, start, mid, end);
}
}
int main() {
int n, i;
scanf("%d", &n);
int array[n];
for(i = 0; i < n; i++) scanf("%d", &array[i]);
mergeSort(array, 0, n-1);
printf("%lld\n", count);
return 0;
}