[JAVA/백준] 1517번 : 버블 소트

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

버블 소트는 서로 인접해 있는 두 수를 바꿔가며 정렬하는 방법이다. 예를 들어 수열이 3 2 1 이었다고 하자. 이 경우에는 인접해 있는 3, 2가 바뀌어야 하므로 2 3 1 이 된다. 다음으로는 3, 1이 바뀌어야 하므로 2 1 3 이 된다. 다음에는 2, 1이 바뀌어야 하므로 1 2 3 이 된다. 그러면 더 이상 바꿔야 할 경우가 없으므로 정렬이 완료된다. --> 인접한 값을 바꾸는 버블소트는 그만큼 거슬러 올라간, 즉 스왑이 일어난 횟수를 카운트해주면 된다.

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

<Output>

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

<examples>
-입력

3
3 2 1

-출력

3

[풀이]

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

public class Main {
    public static int[] A,tmp;
    public static long result;

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

    private static void merge_sort(int s, int e) {
        if(e-s<1)
            return;
        int m = s + (e-s) / 2;

        merge_sort(s,m);
        merge_sort(m+1,e);

        for (int i=s;i<=e;i++){
            tmp[i] = A[i];
        }//비교를 위한 tmp배열 저장

        int k = s;
        int idx1 = s;
        int idx2 = m+1;

        while (idx1<=m && idx2<=e){
            if (tmp[idx1] > tmp[idx2]) {
                A[k] = tmp[idx2]; //큰 값을 앞으로 끌고오기-스왑 발생
                result = result + idx2-k; //둘의 차이 값 = 움직인 거리
                k++;
                idx2++;
            }else {
                A[k] = tmp[idx1];
                k++;
                idx1++;
            }
        }
        while (idx1<=m) {
            A[k] = tmp[idx1];
            k++;
            idx1++;
        }
        while (idx2<=e) {
            A[k] = tmp[idx2];
            k++;
            idx2++;
        }
    }
}

 

---

문제를 보자.

 

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

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

--> 인접한 값을 바꾸는 버블소트는 그만큼 거슬러 올라간, 즉 스왑이 일어난 횟수를 카운트해주면 된다.

 

 

값의 최대 범위가 커서 버블 정렬을 곧이 곧대로 사용하면 시간 초과가 일어나므로

O(nlogn)의 시간 복잡도를 가진 '병합 정렬'의 개념을 사용해야 한다.

두 그룹을 쪼개어 인덱스 두 개를 두고 비교해나가는 병합 정렬의 개념에도

버블의 스왑 개념이 포함되어 있는 걸 인지해야 함.

보기엔 두 값을 바꾸는 것이지만, 문제에서는 버블 정렬이 일어난 횟수(result)를 물어보고 있기 때문에

이걸 어떻게 구할지 생각해보면 

사실 두 값을 교환한다는 것은 뒤의 값에서 처음 값을 뺀 값을 의미하므로(A와 B의 차이 = B-A)

스왑이 B-A 만큼 일어났다고 유추해낼 수 있다.

이런 개념을 이용하여 풀면 된다.

 

병합 정렬 문제와 거의 동일하나, 스왑 횟수를 세기 위한 로직이 추가되었다고 보면 될 것 같다..!

이것도 idx1 > idx2 일 때에만 적용이 되는 로직으로 (idx2가 idx1의 자리까지 스왑하여 거슬러 올라오는 정도)

사실 상 크게 다를 것이 없다.