백준_2751 수 정렬하기2 (풀이 참고 코드개선)

기존 코드는 분할 할때마다 새로운 int 배열 두개를 생성해서 정렬하고,

그걸 merge한 배열을 또 새로 만들어서 반환하는 형식

 

에서 다른 코드 참고하고 이해해서 개선했다

 

해당 코드는 정렬을 위한 temp 배열 외에는 다른 배열을 만들지 않고

정렬한 값을 다시 본 입력받은 배열에 저장하는 방식

 

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

public class BJ_2751 {
    static int[] arr, tempArr;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();

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

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

        mergeSort(0, n-1);

        for(int i=0; i<n; i++) {
            sb.append(arr[i]).append('\n');
        }

        System.out.println(sb);
    }

    static void mergeSort(int s, int e) {
        if(e-s < 1) {
            return;
        }

        int m = (e+s)/2;

        mergeSort(s,m);
        mergeSort(m+1,e);

        int i, j;

        for(i=s; i<e+1; i++) {  
            tempArr[i] = arr[i];
        }

        int arrInd = s;
        i = s;
        j = m+1;

        while(i<m+1 && j<e+1) {
            if(tempArr[i] > tempArr[j]) {
                arr[arrInd++] = tempArr[j++];
            } else if (tempArr[i] < tempArr[j]) {
                arr[arrInd++] = tempArr[i++];
            }
        }

        while(i<m+1) {
            arr[arrInd++] = tempArr[i++];
        }

        while(j<e+1) {
            arr[arrInd++] = tempArr[j++];
        }

    }
}

 

 

맨 위 제출이 개선한 코드이다.

속도 뿐만 아니라 메모리도 반 이상 줄었다