백준 1517 버블 소트 Java

정답률 26퍼센트의 분할정복 문제이다. 

내 티스토리 sort카테고리에도 있는

코드를 주고 더이상 정렬할 게 없을 때 몇단계인지 출력하는 그 버블 소트 문제와는 다른 문제이다.

 

다들 알겠지만 N의 최대값이 500,000 오십만이기 때문에

진짜 버블소트 코드로 swap의 횟수를 세면 시간 초과가 나온다.

버블소트는 O(n^2)이고 N이 오십만 이기 때문에 연산 횟수가 너무 많아진다.

 

당연 나와 같은 초보들은 해결법을 떠올릴 수 없을 것이다..

이 문제는 머지소트를 이용해서 해결한다.

 

머지소트에서는 배열을 middle값 기준으로 나눠서

merge를 통해 정렬한다.

 

merge는 하나의 배열을 middle 인덱스를 기준으로 반 반 나누어서

값이 더 작은 쪽이 임시 배열에 순서대로 저장된다.

백준님의 강의자료 중..

이 문제는 이 merge의 과정에서 오른쪽(midle+1 부터 end까지)의

값이 임시배열에 저장될 때 남아있는 왼쪽(start 부터 middle까지)의 크기만큼

더해주면 정답이 된다.

 

이 문제가 어렵다고 생각이 든게 머지소트를 활용해서 정답을 구한다는 것을 생각하기도

어렵지만 익히 알고있는 머지소트를 그대로 사용하면 바로 시간초과가 뜬다.

 

원래는 merge를 하는 과정에서

각각 비교해서 임시배열에 저장하는 while문 한개

앞부분에 값이 남았을 경우 처리하는 while문 한개

뒷부분에 값이 남았을 경우 처리하는 while문 한개

총 세 개의 while문으로 임시배열에 정렬된 값들을 집어넣는데

 

이 문제에서는 while문을 한번만 써서 시간초과를 피해야 한다.

어떻게 while문 한번으로 병합을 하는지는 코드를 보자.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Q1517 {
 
    public static long solve(int[] a, int start, int end) {
        if (start == end) {
            return 0;
        }
        int mid = (start+end)/2;
        int[] b = new int[end-start+1];
        long ans = solve(a, start, mid) + solve(a, mid+1, end);
        {
            int index1 = start; //앞부분 인덱스
            int index2 = mid+1; //뒷부분 인덱스
            int k = 0;
            while (index1 <= mid || index2 <= end) { // &&이 아닌 ||로 while문 하나로 처리
                //index2 > end || ->로 앞부분에 남아있을 경우를 처리
                if (index1 <= mid && (index2 > end || a[index1] <= a[index2])) { 
                    b[k++] = a[index1++];
                } else {
                    ans += (long)(mid-index1+1); //왼쪽의 남은 크기 만큼 더함
                    b[k++] = a[index2++];
                }
            }
        }
        for (int i=start; i<=end; i++) {
            a[i] = b[i-start];
        }
        return ans;
    }
 
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.valueOf(br.readLine());
        int[] a = new int[n];
        String[] line = br.readLine().split(" ");
        for (int i=0; i<n; i++) {
            a[i] = Integer.valueOf(line[i]);
        }
        long ans = solve(a, 0, n-1);
        System.out.println(ans);
    }
}