[백준/JAVA] 2751번 수 정렬하기2

• 시간 복잡도가 O(nlogn)인 정렬 알고리즘으로 풀 수 있습니다. 예를 들면 병합 정렬, 힙 정렬 등이 있지만, 어려운 알고리즘이므로 지금은 언어에 내장된 정렬 함수를 쓰는 것을 추천드립니다.
  https://www.acmicpc.net/problem/2751

1. 문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

2. 문제 접근

1) 수의 개수 N을 입력받는다.
2) N만큼 반복하며 정수를 입력받고 이를 배열에 저장한다.
3) 배열에 저장된 수들을 병합정렬을 이용하여 오름차순으로 정렬한다.
4) 정렬된 배열을 출력한다.

병합정렬

• 리스트 길이가 0 또는 1이면 이미 정렬된 것으로 간주.
• 정렬 되지 않은 리스트는 절반으로 나누어 2개의 리스트로 분할한다.
• 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
• 다시 하나의 정렬된 리스트로 합병한다.
  참고 :https://velog.io/@agfalcon/%EB%B3%91%ED%95%A9%EC%A0%95%EB%A0%AC

3. 코드

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


//병합 정렬 사용
public class Main {    
    static int data[];
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int array[] = new int[N];
        data = new int[N];
        for(int i=0;i<N;i++) {
            array[i] = Integer.parseInt(br.readLine());
        }
        MergeSort(array, 0, N-1);
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<array.length;i++) {
            sb.append(array[i]).append("\n");
        }
        System.out.print(sb);
    }

    private static void Merge(int[] array, int start, int middle, int end) {
        int i = start;
        int j = middle+1;
        int k = start;
        while(i<=middle && j<=end) {
            if(array[i]<array[j]) {
                data[k] = array[i];
                i++;
            }
            else {
                data[k] = array[j];
                j++;
            }
            k++;
        }
        if(i>middle) {
            for(int t = j;t<=end;t++) {
                data[k] = array[t];
                k++;
            }
        }
        else {
            for(int t = i;t<=middle;t++) {
                data[k] = array[t];
                k++;
            }
        }
        for(int t=start;t<=end;t++) {
            array[t] = data[t];
        }
    }

    private static void MergeSort(int[] array, int start, int end) {
        if(start<end) {
            int middle = (start+end)/2;
            MergeSort(array, start, middle);
            MergeSort(array, middle+1, end);
            Merge(array, start, middle, end);
        }
    }
}