[BOJ] 1517. 버블소트2

 

 

 

수열 A에 대해 버블 소트를 수행했을 때, swap이 총 몇 번 발생하는지를 알아내는 문제이다.

 

N의 범위가 최대 500,000이기에 O(n^2)인 버블 소트로 풀이하면 시간 초과가 발생하는 문제가 발생한다. 여기서는 O(NlogN)의 시간복잡도를 가진 병합 정렬을 사용하여 풀이하였다. 두 그룹을 병합하는 과정에서 버블 정렬의 swap이 포함되어 있다는 것을 떠올리는게 포인트였다.

 

 

문제

 

 

 

 

문제 풀이

 

버블 소트에서 swap이 일어나는 조건 : 배열 앞의 숫자가 뒤의 숫자보다 클 때 (A[i] > A[i+n])

result의 자료형을 처음에는 int로 설정했었으나 틀렸다는 결과가 뜨자 long으로 바꾸었더니 통과가 되었다.

아마도 최악의 경우, n의 최대 범위에서 모두 swap이 일어나고, 그 swap 횟수가 int 범위(-2,147,483,648부터 2,147,483,647)를 넘어가는 것으로 짐작했는데..

 

찾아보니 스왑 횟수는 최대 N * (N-1) / 2에 가까운 값을 가질 수 있으며, 이를 최악의 경우에 대입해보면 N이 500,000일 경우, 최대 스왑 횟수는 약 500,000 * 499,999 / 2 = 124,999,750,000 이 되므로 int 타입의 범위를 초과하게 된다.

그러므로 result의 자료형은 int보다 범위가 충분히 넉넉한 long 타입으로 선언하여 쓰는 것이 모든 테스트케이스를 만족하게 될 것이다.

 

 

•  

 

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

// swap 횟수 출력 (버블 정렬)
public class BOJ1517 {
    static int[] arr, tmp;
    // index가 이동한 거리 저장
    static long result = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 수의 개수
        int n = Integer.parseInt(br.readLine());
        arr = new int[n];
        // 정렬 저장할 입시 배열
        tmp = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i=0; i<n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        merge_sort(0, n-1);
        System.out.println(result);
    }

    public static void merge_sort(int start, int end) {
        if (start == end) return;
        int mid = (start + end) / 2;
        merge_sort(start, mid);
        merge_sort(mid+1, end);
        // 병합
        merge(start, mid, end);
    }

    public static void merge(int start, int mid, int end) {
        int idx = start;
        int l = start;
        int r = mid+1;

        while (l <= mid && r <= end) {
            if (arr[l] <= arr[r]) {
                tmp[idx++] = arr[l++];
            } else {
                // 뒤 쪽 데이터 값이 더 작아 선택될 때 swap이 일어났다고 가정
                // 현재 남아 있는 앞쪽 데이터 개수만큼 결과값 더함
                tmp[idx++] = arr[r++];
                result += (r - idx);
            }
        }

        // 남아있는 데이터 정리
        while (l <= mid) {
            tmp[idx++] = arr[l++];
        }

        while (r <= end) {
            tmp[idx++] = arr[r++];
        }

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