[Baekjoon] 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 횟수를 출력한다

예시 입력

예시 출력

JavaScript
복사

JavaScript
복사

풀이 과정

문제 설명에 앞서 버블 소트에 대해 간략하게 설명하겠습니다.

버블 소트란?

원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 버블 소트라는 이름이 지어졌습니다. 버블 소트는 인접한 두 원소를 검사하여 정렬하는 알고리즘입니다. 

예제를 통해 설명해보겠습니다.

5 4 3 2 1 을 오름차순으로 정렬하고자 합니다.

이 때, 어떤 과정을 거치고 몇 번의 swap이 일어날까요?

(1) 4 5 3 2 1 (2) 4 3 5 2 1 (3) 4 3 2 5 1 (4) 4 3 2 1 5 (5) 3 4 2 1 5

(6) 3 2 4 1 5(7) 3 2 1 4 5 (8) 2 3 1 4 5 (9) 2 1 3 4 5 (10) 1 2 3 4 5

그렇다면 정렬이 발생할 때 마다 count를 증가하면 쉽게 구할 수 있지 않을까요?

버블 소트를 간단하게 구현해봅시다.

public void bubbleSort(){
		int [] arr = new int [] {5,4,3,2,1};
		int count = 0;

		for(int i = 0; i < arr.length; i++){
				for(int j = i+1; j <arr.length; j++) {
						if (arr[i] < arr[j]){
								swap(arr[i], arr[j]);
								count++;
						}
				}
		}
}
Java
복사

알고리즘 스터디 8개월 짬밥의 여러분들은 쉽게 눈치채셨겠지만 O(n^2) 인 것을 확인할 수 있습니다.

그렇다면 어떻게 해결해야될까요?

머지 소트를 사용하자 

“버블 소트로 구현하라고 했는데 머지 소트? 이거 완전 날먹 아닌가요? (김소연, 소프트 20)”

머지 소트는 정렬을 분할 정복으로 구현한 것입니다. 이 문제에서 중요한건 어떻게 정렬하는가가 아닌, 머지 소트로 정렬할 때 어떻게 swap 횟수를 기록할 것인가 입니다.

핵심은 “자기 보다 큰 수의 개수 만큼 count를 더한다” 입니다.

최종 코드

package baekjoon.divide_and_conquer;

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

public class _1517 {

    static long answer;
    static long[] A, B;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        A = new long[N];
        B = new long[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
        divide_conquer(0, N - 1);
        System.out.println(answer);
    }

    static void divide_conquer(int low, int high) {
        if (low < high) {
            int mid = (low + high) / 2;
            divide_conquer(low, mid);
            divide_conquer(mid + 1, high);
            merge(low, mid, high);
        }
    }

    static void merge(int low, int mid, int high) {
        int leftIndex = low;
        int rightIndex = mid + 1;
        int index = low;

        while (leftIndex <= mid && rightIndex <= high) {
            if (A[leftIndex] <= A[rightIndex]) {
								B[index] = A[leftIndex];
								leftIndex++;
            } else {
								B[index] = A[rightIndex];
								rightIndex++;
								answer += (mid + 1 - leftIndex);
            }
            index++;
        }

        while (leftIndex <= mid) {
            B[index] = A[leftIndex];
            leftIndex++;
            index++;
        }

        while (rightIndex <= high) {
            B[index] = A[rightIndex];
            rightIndex++;
            index++;
        }

        for (int i = low; i < high + 1; i++) {
            A[i] = B[i];
        }

    }

}
JavaScript
복사