[백준] 1517 : 버블소트 JAVA 풀이

 

처음 문제를 읽었을 때는 쉬워보이는데 정답 비율이 왜 이렇게 낮지?라는 생각이 들었다.

그리고 버블소트로 풀어보니 역시나 시간초과가 나왔다.

버블소트는 시간복잡도가 O(N^2)인데, 최대 500,000개의 수가 주어지니 그럴 만했다.

 

swap횟수는 병합정렬을 하는 과정에 뒤쪽에 있던 인덱스가 앞으로 이동한 만큼 더해주면 된다.

 

import java.io.*;
import java.util.*;
public class Main{
    static long cnt = 0;
    static long[] sorted;
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        
        long[] arr = new long[n];
        sorted = new long[n];
        
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        for(int i=0;i<n;i++){
            arr[i] = Long.parseLong(st.nextToken());
        }
        
        mergeSort(arr, 0, n-1);
        
        System.out.println(cnt);
        
    }
    
    static void mergeSort(long[] arr,int low, int high){
        if(low<high){
            int mid =(low+high)/2;
            mergeSort(arr, low, mid);
            mergeSort(arr, mid+1, high);
            merge(arr, low, mid, high);
        }
    }
    
    static void merge(long[] arr, int low, int mid, int high){
        int l = low;
        int r = mid+1;
        int idx = low;
        
        while(l <= mid && r <= high){
            if(arr[l]<=arr[r]){
                sorted[idx++] = arr[l++];
            }
            else{
                sorted[idx++] = arr[r++];
                cnt += (r-idx);
            }
        }
        
        
        while(r<=high){
            sorted[idx++] = arr[r++];
        }
        
        
        while(l<=mid){
           sorted[idx++] = arr[l++];
        }
        for(int i=low;i<=high;i++){
            arr[i] = sorted[i];
        }
    }
}