문제 번호 2751번 : 수 정렬하기 2 - JAVA [자바]

https://www.acmicpc.net/problem/2751

2751번: 수 정렬하기 2

문제 설명

 

수를 정렬 한 후 출력하는 문제입니다.

 

 

문제 풀이

해당 문제에서 가장 중요한 것은 속도입니다.

속도가 걸려서 문제를 풀지 못하는 경우가 많습니다.

제가 아는 빠른 정렬은 합병 정렬과 힙 정렬, 카운팅 정렬입니다.

지금 포스팅 되어 있는 정렬은 합병 정렬임으로 합병 정렬로 해당 문제를 해결해 보겠습니다.

합병 정렬에 관해서는 이 글에서 참고하시면 됩니다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();

        int count = sc.nextInt();

        int[] array = new int[count];

        for(int i=0; i<array.length; i++){
            array[i] = sc.nextInt();
        }

        Merge_sort.merge_sort(array);

        for(int value : array){
            sb.append(value).append('\n');
        }
        System.out.println(sb);


    }
}

class Merge_sort {
    private static int[] sort_array;// 새로운 정렬을 저장할 배열

    public static void merge_sort(int[] array){
        sort_array = new int[array.length];
        merge_sort(array, 0, array.length - 1);
        sort_array = null;
    }

    /*
    * [BOTTOM-UP] 방식
    * 아래서 부터 위로 올라면서 바로 병합하기 때문에 BOTTOM-UP 방식이라고 한다.
    * 이중 반복문을 사용해서 list 길이가 1인 것부터 점점 늘려가는 형식의 함수이다.
    */
    private static void merge_sort(int[] array, int first, int second){
        /*
        * list_size을 기준으로 1일때 2일때 4일때.. 배열의 인덱스의 규칙이 같음으로
        * 해당 list_size을 기준으로 반복문을 먼저 돌립니다.
        * 해당 list_size는 최대값이 전체 배열의 길이를 넘을 수 없음으로 second까지를 최대값으로 설정합니다.*/
        for(int list_size = 1; list_size<=second; list_size+=list_size){
            /*
            * left는 각 서브리스트의 첫번쨰 인덱스를 의미합니다.
            * 각 서브리스트의 첫번째 인덱스의 규칙은 left에서 길이의 2배 만큼 더하면 됩니다.
            * 그래서 list_size*2를 해줍니다.
            * left값은 마지막 인덱스 값보다 커질 수 없습니다.
            * 하지만 중간값을 구할 때 outofindex 에러가 날 수 있으니 list_size만큼은 뺴줍니다.
            * left는 마지막 서브 리스트의 mid 인덱스 만큼 역시 커질 수 없습니다.*/
            for(int left = first; left <= second-list_size; left+=(list_size*2)){
                int l = left; // 각 서브 리스트의 첫 번째 값
                int r = left + (list_size*2) -1; // 각 서브리스트의 다음 첫 번째 인덱스에서 1일빼서 마지막 인덱스를 구함
                int m = left + list_size-1; // left에서 사이즈 만큼 더하면 중간값이 나오게 됩니다. 인덱스는 0부터 시작함으로 -1을 해줍니다.
                merge(array,l,m,Math.min(r,second));
            }
        }

    }

    private static void merge(int[] array, int first, int mid, int second){
        int l = first;//왼쪽의 비교할 서브 리스트의 인덱스
        int m = mid+1;//오른쪽의 비교할 서브 리스트의 인덱스
        int index = first;//비교 한 후 입력할 배열

        //외쪽과 오른쪽 둘 중 하나의 서브 리스트의 비교가 끝나면 while문을 종료합니다.
        while(l<=mid && m<=second){
            //왼쪽 서브리스트와 오른쪽 서브 리스트를 비교하면서 정렬 배열에 입력합니다.
            if(array[l] <= array[m]){
                sort_array[index] = array[l];
                l++;
                index++;
            }
            else{
                sort_array[index] = array[m];
                m++;
                index++;
            }
        }

        /*
        * 왼쪽 서브 리스트와 오른쪽 서브 리스트가 정렬 배열에 입력되지 않고 남았을경우
        * 이미 서브 리스트는 정렬이 되어 있는 상태임으로 정렬된 리스트 뒤에 붙입니다.
         */
        while(l<=mid){
            sort_array[index] = array[l];
            l++;
            index++;
        }
        while(m<=second){
            sort_array[index] = array[m];
            m++;
            index++;
        }

        //정렬된 배열의 값을 배열에 입력합니다.
        for(int i=first; i<=second; i++){
            array[i] = sort_array[i];
        }

    }

}

 

여기서 한가지 주의해야 할 점은 그냥 바로 System.out.println() 로 사용해서 출력하면 속도 때문에 에러가 납니다.StringBuilder를 이용해서 출력 해야합니다. 합병 정렬을 이해하셨다면 무리 없이 문제를 푸실 수 있을겁니다.