[JAVA][Baekjoon] 1517번 버블 소트 🌟🌟🌟

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

 

📌 접근 방식

제목은 버블 소트이지만, N의 최대 범위가 500,000이므로 버블 정렬을 이용한다면 시간 초과가 발생한다!

➡️ 그래서 O(nlogn)의 시간 복잡도를 가진 병합 정렬을 사용해 풀어보았다

[알고리즘] 병합 정렬(Merge Sort)이란?

 

여기서 버블 정렬의 swap의 횟수는 이동한 index로 계산하면 된다!

 

 

✅ PASS CODE

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

public class Main {
    public static int[] arr, tmp;
    public static long sum;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        arr = new int[N];
        tmp = new int[N];
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        sum = 0;
        mergeSort(0, N-1);
        System.out.println(sum);
    }
    public static void mergeSort(int s, int e) {
        if(e-s < 1) return;
        int m = (s+e)/2;
        mergeSort(s, m);
        mergeSort(m+1, e);

        for(int i = s; i <= e; i++) {
            tmp[i] = arr[i];
        }

        int k = s;
        int index1 = s;
        int index2 = m+1;
        while(index1 <= m && index2 <= e) {
            if(tmp[index1] > tmp[index2]) {
                arr[k] = tmp[index2];
                if(index2 > k) sum += (index2 - k);
                k++;
                index2++;
            }
            else {
                arr[k] = tmp[index1];
                k++;
                index1++;
            }
        }
        while(index1 <= m) {
            arr[k] = tmp[index1];
            k++;
            index1++;
        }
        while(index2 <= e) {
            arr[k] = tmp[index2];
            k++;
            index2++;
        }
    }
}

 

 

 

 

😅 느낀점

처음에는 단순히 swap의 횟수를 구하기 위해 int를 사용했는데 계속 틀렸다고 했다.. 다른 코드들도 잘 구현되어 있고, 입력 예제를 입력하면 잘 출력되는데 뭐가 틀렸는지 계속 고민했다.. 설마설마 하고 int를 long으로만 바꾸었을 뿐인데 정답이 나왔다!

아무래도 입력 크기가 커질수록 값이 int의 최대 범위를 초과해서 오버플로우가 발생해 틀린 것 같다.. 이 과정에서 제시된 데이터의 크기가 얼마인지 그에 따라 자료형 선택이 얼마나 중요한지 깨닫게 되었다!

또한, 처음에는 버블 정렬의 swap 횟수를 버블정렬을 이용해 직접 세면서 문제를 풀려고 했지만, 이는 시간 복잡도가 O(N^2)라서 입력 크기가 큰 경우 시간 초과가 발생했다. 그래서 대신 병합 정렬을 사용해서 이동한 Index의 수로 계산해보았다. 병합 정렬의 시간 복잡도는 O(NlogN)이기 때문에 무사히 풀 수 있었다! 🔥