BOJ_1517 : 버블 소트

👉 문제링크

1517번: 버블 소트

---

---

🔸 문제 분석 🔸

• N개의 수로 이루어진 수열을 버블 소트로 정렬했을 때, swap이 총 몇 번 발생하는지 출력한다.

🔸 문제 풀이 🔸 

• N이 50만까지 가므로 O(nlogn)의 알고리즘을 사용해야 한다.
  • 여기서는 병합 정렬(Merge Sort)을 사용한다.
• 버블 소트는 1칸씩 이동할 수 있으므로, 정렬 후 바뀐 인덱스의 크기를 모두 더하면 된다.
  
  • 병합 정렬에서 기존 인덱스보다 앞 인덱스로 옮길 때, 그 크기를 누적해서 출력한다.

🔸 코드 🔸

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

public class Main {

    private static int[] arr, temp;
    private static long result;

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

        int N = Integer.parseInt(br.readLine());
        arr = new int[N];
        temp = new int[N];

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

        result = 0;
        merge_sort(0, N - 1);

        bw.write(Long.toString(result));
        bw.flush();
    }

    private static void merge_sort(int start, int end) {
        if (end - start < 1) return;

        int mid = start + (end - start) / 2;
        int tempIdx = start;
        int left = start;
        int right = mid + 1;

        merge_sort(left, mid);
        merge_sort(right, end);

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

        while (left <= mid) {
            temp[tempIdx++] = arr[left++];
        }
        while (right <= end) {
            temp[tempIdx++] = arr[right++];
        }

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

🔸 코드 해석 🔸

• 기본적인 병합정렬을 구현하는데, 인덱스 이동을 result에 카운트하는 부분만 차이가 있다.
  • 앞뒤 이동 모두 세면 중복되므로, 인덱스가 앞으로 이동할 때만 카운트했다.
  • left 혹은 right에서 남은 원소들을 처리해주는 부분은 인덱스가 같거나 크므로, result를 카운트하지 않는다.

---

🔸 end 🔸

• 병합 정렬을 직접 구현하는건 처음인데, 사소한 부분들을 실수한게 너무 많았다.
  • merge_sort()메서드에서 start와 end로 범위를 제한해야 하는데, start 대신 0을 사용했었다.
  • left, right의 남은 원소들을 temp로 복사하는 코드를 누락했었다.
  • result를 카운트하는 부분을 인덱스가 커지는쪽도 포함시켜서 중복 카운트가 되었다.
• 그래도 사소한 부분들을 다 틀려보아서, 병합 정렬에 대한 공부가 잘 된 것 같다.
• 세그먼트 트리로도 풀이가 되어 보이는데, 나중에 다시 풀어볼 생각이다.