[Baekjoon] 2751번: 수 정렬하기 2

2751번: 수 정렬하기 2

이 문제는 시간 복잡도가 n log n 이하인 알고리즘을 적용하여 풀어야 하는 문제였습니다. 저는 병합 정렬을 사용하여 해결하였습니다.

처음에는 계속 시간 초과가 나오길래 뭔가 싶었는데 res 배열을 MergeTwoArea에서 만들어서 나온 것이었습니다. static으로 선언하니 해결되었습니다. 인스턴스 변수로 선언하면 1,000,000 과 같은 큰 크기의 배열을 계속 만들어내서 발생한 문제였던 것 같습니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

class Main {
    static int res[];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());

        int[] arr = new int[n];
        res = new int[n];

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

        MergeSort(arr, 0, arr.length - 1);

        for (int j : arr) {
            bw.write(j + "\n");
        }
        
        br.close();
        bw.close();
    }

    static void MergeTwoArea(int[] arr, int left, int mid, int right) {
        int fIdx = left;
        int rIdx = mid + 1;
        int sIdx = left;

        while (fIdx <= mid && rIdx <= right) {
            if (arr[fIdx] <= arr[rIdx]) {
                res[sIdx] = arr[fIdx++];
            } else {
                res[sIdx] = arr[rIdx++];
            }
            sIdx++;
        }

        if (fIdx > mid) {
            for (int i = rIdx; i <= right; i++, sIdx++) {
                res[sIdx] = arr[i];
            }
        } else {
            for (int i = fIdx; i <= mid; i++, sIdx++) {
                res[sIdx] = arr[i];
            }
        }

        for (int i = left; i <= right; i++) {
            arr[i] = res[i];
        }
    }

    static void MergeSort(int[] arr, int left, int right) {
        int mid;

        if (left < right) {
            mid = (left + right) / 2;

            MergeSort(arr, left, mid);
            MergeSort(arr, mid + 1, right);

            MergeTwoArea(arr, left, mid, right);
        }
    }
}