[백준] 버블 소트(1517)

문제

[백준] 버블 소트(1517)

N개의 수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에 대해서 버블 소트를 수행할 때, Swap이 총 몇 번 발생하는지 알아내는 프로그램을 작성하시오.

버블 소트는 서로 인접해 있는 두 수를 바꿔가며 정렬하는 방법이다. 예를 들어 수열이 3 2 1 이었다고 하자. 이 경우에는 인접해 있는 3, 2가 바뀌어야 하므로 2 3 1 이 된다. 다음으로는 3, 1이 바뀌어야 하므로 2 1 3 이 된다. 다음에는 2, 1이 바뀌어야 하므로 1 2 3 이 된다. 그러면 더 이상 바꿔야 할 경우가 없으므로 정렬이 완료된다.

입력

첫째 줄에 N(1≤N≤500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0≤|A[i]|≤1,000,000,000의 범위에 들어있다.

출력

첫째 줄에 Swap 횟수를 출력한다

해설

해당 문제는 버블정렬(Bubble Sort)를 사용해 Swap 횟수를 찾으면 시간복잡도가 O(n2)으로 TLE(Time Limit Exceeded)가 발생할 수 있다.

결국 이 문제는 Swap의 횟수를 구하는 문제이기 때문에 합병정렬(Merge Sort)로도 풀이할 수 있었다.

그렇다면 Swap 횟수를 어떻게 구할 수 있을까?
분할한 원소들을 합치는 과정(merge)을 생각해보면 오름차순 정렬 시 배열의 왼쪽엔 작은 값이 오른쪽엔 큰 값이 와야한다. 즉, left와 right로 분할이 되어있고 right의 값이 left의 값들보다 작은지 비교를 해야한다.

left의 원소가 [4, 5]이고 right의 원소가 [1, 3]이라고 가정했을 때, right의 1원소는 left의 4원소와 5원소 두 가지와 비교 한 뒤 가장 작은 원소로 정해지면서 배열에 저장된다. 즉, 2번의 비교를 한 것이다. right의 3원소의 비교까지 끝나면 총 Swap 횟수는 4번이 되는 것이며 Swap 횟수는 right의 현재 원소보다 큰 left 원소들의 수 이다.

처음엔 이러한 방법으로 풀이했는데도 시간초과가 발생했는데, 그 이유가 merge method에서의 temp(merge 결과 배열) 선언이었는데, temp를 전역변수로 바꿔주니 통과가 되었다.

참고 블로그
https://hoho325.tistory.com/136
https://bcp0109.tistory.com/49

풀이

import java.util.*;
import java.io.*;

public class Main {
	static long answer;
	static long[] arr, temp;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		arr = new long[N];
		temp = new long[N];

		for (int i = 0; i < N; i++) {
			arr[i] = Long.parseLong(st.nextToken());
		}

		answer = 0;
		
		// mergeSort 사용
		mergeSort(0, N - 1);

		System.out.println(answer);
	}

	public static void mergeSort(int start, int end) {
		if(start < end) {
			int mid = (start + end) / 2;
			mergeSort(start, mid);
			mergeSort(mid + 1, end);
			merge(start, mid, end);
		}
	}

	public static void merge(int start, int mid, int end) {
		int left = start;
		int right = mid + 1;
		int index = start;

		while (left <= mid && right <= end) {
			if (arr[left] <= arr[right]) {
				temp[index++] = arr[left++];
			} else {
				answer += mid + 1 - left;
				temp[index++] = arr[right++];
			}
		}

		while (left <= mid) {
			temp[index++] = arr[left++];
		}

		while (right <= end) {
			temp[index++] = arr[right++];
		}

		for (int i = start; i <= end; i++) {
			arr[i] = temp[i];
		}
	}
}