[백준] 1517번: 버블 소트 - java

문제

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

1517번: 버블 소트

 

접근법

원래 세그먼트 트리 연습을 하려고 세그먼트 트리 문제를 고른거였는데 세그먼트 트리로 푸는 것보다 분할 정복으로 푸는게 훨씬 쉽다.. 세그먼트 트리는 다른 문제로 연습을 하는 것이 좋은 것 같다. 따라서 이번 글에서는 합병 정렬(분할 정복의 대표적인 예)을 사용해 푸는 것을 설명해보겠다.

 

과정

{9, 1, 7, 4} 데이터 셋이 있을 때, 합병 정렬 과정은 아래와 같다.

분할하는 과정은 중요하지 않다. 그냥 합병 정렬 하는 것처럼 하면 된다.

중요한 것은 합칠 때이다. 대충 생각해봤을 때, 합칠 때 순서가 바뀌는 경우가 있다면 그게 swap 아닐까? 라는 생각이 들었다.

 

합치는 과정을 살펴보자. 여기서 하나의 아이디어를 찾아야된다. 만약 {1, 2, 3, 4}와 같은 이미 정렬된 배열을 합친다고 생각해보자. 즉, left = {1, 2}, right = {3, 4} 인 것이다. 이미 정렬된 배열은 left 값 모두 right 보다 작다. 즉, 우리가 만들고자 하는 최종 배열의 상태는 left보다 right에 있는 값들이 더 커야한다. 만약 right에 있는 값이 더 작다면 swap이 필요한 것이다.

 

left와 right 각각 가리키는 인덱스 값을 비교해 작은 값을 sorted에 복사한다. left에 있는 값이 더 작으므로 복사해준다. 앞에서 말했듯이 이미 정렬된 상태라면 left에 있는 값이 더 작다. 따라서 left에 있는 값이 sorted에 복사되는 과정은 중요하지 않다. 그저 복사되는 것 뿐이다.

 

이번에는 right에 있는 값이 더 크다. 따라서 swap이 필요하다. swap이 몇번 발생할지 생각해보자. 위에서 말했듯이 우리가 원하는 최종 배열은 left가 right보다 작은 배열이다. 현재 상황에서 4는 left 배열로 가야한다. 즉, 4는 left 배열에서 아직 sorted 배열에 복사되지 않은 애들을 모두 건너뛰어야 된다는 것이다. left 배열에서 아직 sorted 배열에 복사되지 않은 값은 9 한 개이다. 4는 9만 뛰어 넘으면 된다. (swap = 1)

 

이번에도 right에 있는 값이 더 크다. 따라서 left 배열에 남아있는 수를 계산해 swap 횟수에 더해준다.(swap = 2) 이 과정이 끝나면 right 배열을 가리키는 인덱스가 배열의 범위를 넘어가기 때문에 while 문이 끝나게 되고, 남아있는 수를 sorted에 복사해주는 while문으로 넘어가게 될 것이다. 만약 right에 수가 남아있다고 하더라도 left에 남은 수가 없기 때문에 swap 횟수는 더 이상 계산하지 않아도 된다.

 

참고로 현재 swap 값은 2이지만, 이전 합치는 과정에서 swap이 발생했다면 누적해서 더해주어야 한다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static int N;
    static int[] A, sorted;
    static long answer = 0;

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

        N = Integer.parseInt(br.readLine());

        A = new int[N];
        sorted = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }

        mergeSort(0, N - 1);

        System.out.println(answer);
    }

    private static void mergeSort(int left, int right) {
        if (left >= right) {
            return;
        }

        int mid = (left + right) / 2;

        mergeSort(left, mid);
        mergeSort(mid + 1, right);
        merge(left, mid, right);
    }

    private static void merge(int left, int mid, int right) {
        int L = left;
        int R = mid + 1;
        int idx = left;

        while (L <= mid && R <= right) {
            if (A[L] <= A[R]) {
                sorted[idx++] = A[L++];
            } else {
                answer += (mid + 1 - L);
                sorted[idx++] = A[R++];
            }
        }

        // 남아있는 수 처리해주기
        while (L <= mid) {
            sorted[idx++] = A[L++];
        }
        while (R <= right) {
            sorted[idx++] = A[R++];
        }

        // 원본 배열에 복사
        for (int i = left; i <= right; i++) {
            A[i] = sorted[i];
        }
    }
}