BOJ P5 1517 버블 소트 : Java
문제 분석
문제의 제목은 버블 소트이지만 N의 범위가 최대 500,000이므로 버블 소트로 구현하려 한다면 시간 복잡도 가 되어버려 제한 시간을 초과한다.
따라서 이 문제를 제한 시간 안에 풀기 위해서는 더 빠른 시간 복잡도를 가진 알고리즘을 사용해야 한다. 버블 소트보다 빠른 시간 복잡도를 가진 알고리즘은 다음 알고리즘 등이 있다.
| 정렬 알고리즘 | 시간 복잡도 Big O | 비고 |
|---|---|---|
| 버블 정렬 (Bubble Sort) | ||
| 병합 정렬 (Merge Sort) | two-way merge sort 시 | |
| 퀵 정렬 (Quick Sort) | pivot 설정 방식에 따라 성능이 크게 차이 남 | |
| 기수 정렬 (Radix Sort) | k = 데이터의 최대 자릿수 |
이 문제가 요구하는 답은 버블 소트 실행 시 총 몇 번의 swap이 일어나는지 여부인데 다른 정렬 알고리즘을 사용하여 이 문제를 풀기 위해서는 버블 소트 수행 시 일어나는 swap에 대하여 알아볼 필요가 있겠다.
// 정렬 전 배열
arr = {4, 3, 1, 2}
// 첫 번째 for문 수행 시 swap 횟수 = 3 (arr[0]의 4가 arr[3]까지 swap)
arr_1 = {3, 1, 2, 4}
// 두 번째 for문 수행 시 swap 횟수 = 2 (arr[0]의 3이 arr[2]까지 swap)
arr_2 = {1, 2, 3, 4} // 최종 답과 같음
// 정렬 후 배열의 최종적인 모습
arr_sorted = {1, 2, 3, 4}버블소트의 과정을 본다면
첫 번째 for loop 수행 시 0번 index의 4가 3번 index까지 가기 위해 3번의 swap이 일어난다.
두 번째 for loop 수행 시 0번 index의 3이 2번 index까지 가기 위해 2번의 swap이 일어난다.
따라서 총 swap 횟수는 5이다.
여기서 생각해볼 점이 두 가지 있다.
첫 번째로 버블소트를 수행할 때 한 번의 for loop 안에서 특정 값이 swap으로 인해 오른쪽으로 옮겨갈 수 있는 최대 거리는 배열의 길이 - 1 (= arr.length - 1)인데 반해 왼쪽으로 옮겨갈 수 있는 최대 거리는 1이라는 것이다. 위의 예시에서 버블소트 방식으로 첫 번째 for loop 수행 시 arr[0] = 4는 오른쪽으로 3만큼 이동하는데 반해 3, 1, 2의 값들은 모두 1만큼 왼쪽으로 이동한다.
이로 인해 버블 소트 수행 시 일어나는 swap의 총 횟수를 알 수가 있다. 정렬 전 배열의 매 인덱스에서 해당 인덱스의 왼쪽에 위치한 값들 중에 인덱스의 값보다 큰 값의 수를 더한 것이 총 swap 횟수가 된다. 이것이 두 번째 성질이다. 그 이유는 정렬 전 배열에서 자신보다 큰 값이 왼쪽에 위치해있다면 그 값은 배열 과정에서 꼭 자신과 한 번 swap이 일어나기 때문이다. 예를 들어 예시의 정렬 전 배열에서 arr[1] = 3은 자신보다 왼쪽에 위치한 4와 배열 과정에서 swap을 해야 한다. arr[2] = 1은 배열 과정에서 자신보다 왼쪽에 위치한 4, 3과 swap을 해야 한다. 마찬가지로 arr[3] = 2는 4, 3과 swap을 하게 된다. 이로 인해 1 + 2 + 2 = 5가 총 swap 횟수가 되고 이는 정답과 같다. (이 두 개념만을 이용하여 풀 수 있는 문제는 BOJ G2 1377 버블소트가 있다. 이 문제에 대한 분석 역시 추후 올릴 예정이다.)
그렇다면 정답을 완전 탐색(Brute-force)으로 풀 수도 있다. 모든 인덱스를 돌며 해당 인덱스보다 작은 인덱스에서 보다 더 큰 값의 수를 세면 되는 것이다. 하지만 이러한 방법의 시간 복잡도는 버블 소트와 마찬가지로 이므로 사용할 수가 없다.
따라서 이 문제를 풀기 위해서는 두 가지 조건을 충족하는 정렬 알고리즘을 사용해야 한다.
-
시간제한(1초) 안에 수행될 수 있는 알고리즘이어야 한다. 문제에서 주어진 1 <= N <= 500,000 이라면 위의 표에 주어진 의 시간 복잡도를 갖는 병합 정렬, 퀵 정렬, 기수 정렬 모두 제한시간 안에 수행을 마칠 수 있다.
-
버블 소트와 마찬가지로 데이터를 비교하며 찾는 '비교 정렬'이자 '안정 정렬'이어야 한다. 두 데이터 값을 비교하며 swap이 일어나기 때문에 비교 정렬이어야 하며 비교하는 두 값이 같을 때는 swap이 일어나지 않기 때문에 안정 정렬이어야 한다. 1번 조건을 통과한 세 정렬 알고리즘 중 두 가지 조건을 모두 충족하는 방식은 병합 정렬밖에 없다. 퀵 정렬은 비교 정렬이지만 불안정 정렬이고 기수 정렬은 비교 정렬이 아니다.
1, 2번 조건에 의해 이 문제는 병합 정렬(Merge Sort)을 사용하여 푸는 것이 좋겠다.
병합 정렬에 대한 자세한 설명은 추후에 올리기로 한다.
병합 정렬 역시 swap과 비슷한 유사한 효과가 발생하는데 서로 인접한 두 값끼리 swap이 발생하는 버블 정렬과 달리 병합 정렬은 서로 떨어져 있는 두 부분배열의 값들을 비교한 후 더 작은 값을 결과로 출력할 배열에 차곡차곡 쌓는다. 이 때 만약 오른쪽 부분배열의 비교값이 왼쪽 부분배열의 비교값보다 작아서 기존 인덱스보다 왼쪽에 해당 값이 쌓이게 된다면, 기존 인덱스와 결과배열에 삽입될 인덱스의 차이만큼 swap이 발생한 것과 마찬가지인 효과가 일어난다. 따라서 이 차이를 모두 합하면 버블 정렬의 총 swap 횟수와 같은 값이 되는 것이다.
의사 코드 (Pseudo Code)
N(정렬할 수의 갯수)
arr(정렬할 배열)
cnt(swap 횟수 저장할 변수 -> 정답으로 출력)
sorted(배열 병합 시 결과를 저장할 임시 배열 -> 병합을 마친 후 arr에 저장)
// main 함수 구현
for (N의 갯수만큼)
{ arr 선언 }
merge sort 수행하기
cnt 출력
// merge sort 구현
mergeSort(배열 arr)
{ mergeSortHelp(arr, 시작점, 종료점) }
// Top-Down 방식(= 재귀)으로 구현
mergeSortHelp(배열 arr, 시작점 left, 종료점 right) {
mid(중간점)
// 왼쪽, 오른쪽 부분배열 정렬하기
mergeSortHelp(arr, left, mid)
mergeSortHelp(arr, mid+1, right)
// 정렬한 두 부분배열 합치기
merge(arr, left, mid, right)
}
// Bottom-Up 방식으로 구현
mergeSortHelp_BU(배열 arr, 시작점 left, 종료점 right){
for 부분배열 사이즈 size from 1 ~ right, size만큼 증가 {
for 시작점 i from left ~ right - size; 2*size만큼 증가 {
start(왼쪽 부분배열 시작점)
mid(왼쪽 부분배열 종료점, 오른쪽 부분배열 시작)
end(오른쪽 부분배열 종료점)
두 부분배열 merge
}
}
}
// merge 구현
merge(배열 arr, 시작점 left, 중간점 mid, 종료점 right) {
l(왼쪽 배열 시작점)
r(오른쪽 배열 시작점)
idx(결과배열에 저장할 인덱스)
while (l <= mid && r <= right){
오른쪽 배열의 데이터값이 더 작아 선택될 때
swap이 일어났다고 가정하고, 현재 남아있는 앞쪽 인덱스 갯수만큼을 cnt에 더하기
}
남은 데이터 정리하기
}코드 구현 : Java
1. Top-Down 방식 (= 재귀)
public class Main {
static long cnt = 0;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
long[] arr = new long[N];
for (int i = 0; i < N; i++)
arr[i] = Long.parseLong(st.nextToken());
mergeSort(arr);
System.out.println(cnt);
}
static long[] sorted;
public static void mergeSort(long[] arr) {
sorted = new long[arr.length];
mergeSortHelp(arr, 0, arr.length-1);
sorted = null;
}
private static void mergeSortHelp(long[] arr, int left, int right) {
if (left == right) return;
int mid = (left + right)/2;
mergeSortHelp(arr, left, mid);
mergeSortHelp(arr, mid+1, right);
merge(arr, left, mid, right);
}
private static void merge(long[] arr, int left, int mid, int right) {
int l = left;
int r = mid+1;
int idx = left;
while (l <= mid && r <= right) {
if (arr[l] <= arr[r]) {
sorted[idx++] = arr[l++];
}
else {
cnt += r - idx;
sorted[idx++] = arr[r++];
}
}
while (l <= mid) {
sorted[idx++] = arr[l++];
}
while (r <= right) {
sorted[idx++] = arr[r++];
}
for (int i = left; i <= right; i++)
arr[i] = sorted[i];
}
}2. Bottom-Up 방식
public class Main {
static long cnt = 0;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
long[] arr = new long[N];
for (int i = 0; i < N; i++)
arr[i] = Long.parseLong(st.nextToken());
mergeSort(arr);
System.out.println(cnt);
}
static long[] sorted;
public static void mergeSort(long[] arr) {
sorted = new long[arr.length];
mergeSortHelp_BU(arr, 0, arr.length-1);
sorted = null;
}
private static void merge(long[] arr, int left, int mid, int right) {
int l = left;
int r = mid+1;
int idx = left;
while (l <= mid && r <= right) {
if (arr[l] <= arr[r]) {
sorted[idx++] = arr[l++];
}
else {
cnt += r - idx;
sorted[idx++] = arr[r++];
}
}
while (l <= mid) {
sorted[idx++] = arr[l++];
}
while (r <= right) {
sorted[idx++] = arr[r++];
}
for (int i = left; i <= right; i++)
arr[i] = sorted[i];
}
private static void mergeSortHelp_BU(long[] arr, int left, int right) {
if (left == right) return;
for (int size = 1; size <= right; size += size) {
for (int l = left; l <= right-size; l += 2*size) {
int start = l;
int mid = l + size - 1;
int end = Math.min(l + 2*size - 1, right);
merge(arr, start, mid, end);
}
}
}
}유의점
- Top-Down 방식과 Bottom-Up 방식 두 가지 모두로 구현해보았다. 코딩 테스트 시 재귀는 최대한 피하는 것이 좋다는 말을 들어서(?) 웬만하면 실제 테스트 시 Bottom-Up 방식으로 구현하는 것이 좋을 듯 싶다.
