[백준 2751] 수 정렬하기 2 (Java) - Arrays.sort() vs Merge Sort

🚀 문제 분석

• 데이터 규모: $N=1,000,000$ (100만 개)
• 시간 제한: 2초
• 핵심 과제: $O(N \log N)$의 시간 복잡도를 상시 보장하거나, 자바 내부 최적화를 활용하여 대량의 데이터를 안정적으로 정렬해야 합니다.

💡 두 가지 해결 전략

1. Arrays.sort() 활용 (실전형)

가장 빠르고 간결한 방법입니다. Java의 Arrays.sort(int[])는 Dual-Pivot Quicksort를 사용하여 평균적으로 매우 뛰어난 성능을 보입니다. 대다수의 코딩 테스트 케이스를 통과할 수 있지만, 최악의 경우($O(N^2)$)를 저격하는 데이터가 있을 경우 리스크가 존재합니다.

2. Merge Sort 구현 (방어형)

어떤 데이터가 들어와도 상시 $O(N \log N)$을 보장하는 병합 정렬을 직접 구현합니다. 분할 정복(Divide & Conquer) 원리를 이용하며, 추가 메모리($O(N)$)를 사용하는 대신 성능의 불확실성을 완전히 제거할 수 있습니다.

---

💻 구현 코드 (Java)

1️⃣ Arrays.sort()를 이용한 풀이

가장 직관적이며, 대량 출력을 위해 StringBuilder를 사용하는 것이 핵심입니다.

import java.io.*;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] nums = new int[n];
        
        for (int i = 0; i < n; i++) nums[i] = Integer.parseInt(br.readLine());

        Arrays.sort(nums); // 평균 O(N log N)

        StringBuilder sb = new StringBuilder();
        for (int num : nums) sb.append(num).append("\n");
        System.out.print(sb);
    }
}

2️⃣ Merge Sort를 직접 구현한 풀이

안정성을 최우선으로 고려할 때 사용하는 방식입니다.

import java.io.*;

public class Main {
    static int[] temp;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] nums = new int[n];
        temp = new int[n];

        for (int i = 0; i < n; i++) nums[i] = Integer.parseInt(br.readLine());

        mergeSort(nums, 0, n - 1);

        StringBuilder sb = new StringBuilder();
        for (int num : nums) sb.append(num).append("\n");
        System.out.print(sb);
    }

    static void mergeSort(int[] nums, int s, int e) {
        if (s >= e) return;
        int m = (s + e) >>> 1;
        mergeSort(nums, s, m);
        mergeSort(nums, m + 1, e);
        merge(nums, s, m, e);
    }

    static void merge(int[] nums, int s, int m, int e) {
        int i = s, j = m + 1, k = 0;
        while (i <= m && j <= e) {
            temp[k++] = (nums[i] < nums[j]) ? nums[i++] : nums[j++];
        }
        while (i <= m) temp[k++] = nums[i++];
        while (j <= e) temp[k++] = nums[j++];

        for (int idx = 0; idx < k; idx++) {
            nums[s + idx] = temp[idx];
        }
    }
}

---

🧐 기술적 고찰

• 성능과 안정성 사이의 트레이드 오프: Arrays.sort()는 추가 메모리 없이 빠르지만 최악의 경우(Worst Case)가 존재하고, Merge Sort는 추가 메모리를 쓰지만 최악의 경우에도 일정한 성능을 보장합니다.
• 언어별 차이: 파이썬이나 Java의 객체 정렬(Arrays.sort(Object[]))은 이미 Timsort(병합 정렬의 변형)를 쓰고 있어 안전하지만, Java의 int[] 정렬은 퀵소트 기반이라는 점을 인지하고 있어야 이런 방어적인 코드를 짤 수 있습니다.
• I/O 최적화: 100만 건의 데이터는 알고리즘만큼이나 StringBuilder를 통한 출력 최적화가 합불을 결정짓는 중요한 요소입니다.