[백준 1517] 버블 소트 (Java)

🚀 문제 분석: 버블 소트인데 버블 소트가 아니다?

문제 이름부터 대놓고 '버블 소트'이고, 목표는 swap 횟수를 구하는 것입니다. 하지만 데이터 개수 $N$이 500,000이라는 점에 주목해야 합니다.

• 버블 소트 ($O(N^2)$): 약 2,500억 번 연산 → 무조건 시간 초과(TLE)
• 진짜 정체: 이 문제는 정렬 과정에서의 Inversion Counting(역전쌍 개수 세기)을 $O(N \log N)$에 해결해야 하는 문제입니다.

💡 인사이트: 왜 인덱스 차이로 안 풀릴까?

지난 1377번 문제에서는 "정렬 전후의 인덱스 차이"만으로 답을 구했습니다. 하지만 그건 '패스(Pass) 횟수'를 묻는 문제였기 때문입니다. 이번처럼 '전체 Swap 횟수'를 물을 때는 최종 위치만 봐서는 그 과정에서 일어난 수많은 '새치기'의 총합을 알 수 없습니다.

여기서 병합 정렬(Merge Sort)이 등판합니다.

🛠️ 해결 전략: 병합 정렬을 활용한 Swap 추적

병합 정렬은 배열을 반으로 나누고 합치는 과정에서 정렬을 수행합니다. 이때 '오른쪽 그룹의 원소가 왼쪽 그룹보다 먼저 선택될 때'가 바로 역전(Swap)이 발생하는 순간입니다.

1. 병합(Merge) 과정: 왼쪽 포인터($i$)와 오른쪽 포인터($j$)를 비교합니다.
2. 역전 발생: 만약 A[i] > A[j]라면, 오른쪽 원소 A[j]는 현재 남아있는 왼쪽 그룹의 모든 원소를 한꺼번에 뛰어넘어 앞으로 이동해야 합니다.
3. 카운팅: 이때 이동하는 거리 j - k (원래 위치 j와 현재 들어갈 위치 k의 차이)가 바로 그 원소가 수행한 swap 횟수가 됩니다.

💻 구현 코드 (Java)

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

public class Main {
    static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int[] temp;

    public static void main(String[] args) throws Exception {
        int N = nextInt();

        temp = new int[N];
        int[] A = new int[N];
        for (int i = 0; i < N; i++) {
            A[i] = nextInt();
        }

        // 전체 swap 횟수는 int 범위를 초과하므로 long 출력
        System.out.println(mergeSort(A, 0, N - 1));
    }

    /**
     * 분할 정복을 통한 병합 정렬 및 Inversion Counting
     */
    static long mergeSort(int[] A, int s, int e) {
        if (s >= e) return 0;

        int m = (s + e) >>> 1;
        
        // 왼쪽 구간 swap + 오른쪽 구간 swap + 현재 병합 시 발생하는 swap
        return mergeSort(A, s, m) + mergeSort(A, m + 1, e) + merge(A, s, m, e);
    }

    /**
     * 두 구간을 병합하며 역전쌍(Swap) 계산
     */
    static long merge(int[] A, int s, int m, int e) {
        int i = s;      // 왼쪽 구간 포인터
        int j = m + 1;  // 오른쪽 구간 포인터
        int k = s;      // temp 배열 포인터
        long swapCount = 0;

        while (i <= m && j <= e) {
            if (A[i] <= A[j]) {
                temp[k++] = A[i++];
            } else {
                /* * 핵심 로직: 오른쪽 원소가 새치기할 때
                 * 현재 위치(j)에서 들어가야 할 위치(k)를 뺀 값이 
                 * 해당 원소가 뛰어넘은(swap한) 원소의 개수입니다.
                 */
                swapCount += (long) (j - k);
                temp[k++] = A[j++];
            }
        }

        // 남은 왼쪽 구간 원소 처리
        while (i <= m) {
            temp[k++] = A[i++];
        }

        // 남은 오른쪽 구간 원소 처리
        while (j <= e) {
            temp[k++] = A[j++];
        }

        // 정렬된 temp 배열을 원본 배열 A에 복사
        for (k = s; k <= e; k++) {
            A[k] = temp[k];
        }

        return swapCount;
    }

    /**
     * Fast I/O를 위한 정수 입력 메소드
     */
    static int nextInt() throws Exception {
        while (st == null || !st.hasMoreTokens()) {
            st = new StringTokenizer(br.readLine());
        }
        return Integer.parseInt(st.nextToken());
    }
}

🧐 기술적 고찰

• 자료형의 선택: $N=50$만일 때 역전쌍의 총합은 int 범위를 가볍게 넘어갑니다. 결과값 산출 시 반드시 long을 사용해야 합니다.
• Inversion Counting의 정석: 단순히 순서를 맞추는 도구를 넘어, 데이터의 이동 경로와 거리를 추적하는 프레임워크로서 병합 정렬의 유연성을 다시금 확인했습니다.
• 1377번과의 차이: 결과값만 보고 과정을 유추할 수 있는 문제와, 과정 자체를 낱낱이 기록해야 하는 문제를 구분하는 선구안의 중요성을 배웠습니다.