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

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

<Input>
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

<Output>

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

<examples>
-입력

5
5
4
3
2
1

-출력

1
2
3
4
5

[풀이]

import java.io.*;

public class Main {
    public static int[] A,tmp;
    public static long result;

    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());
        A = new int[N+1];

        tmp = new int[N+1];
        for (int i=1;i<=N;i++){
            A[i] = Integer.parseInt(br.readLine());
        }
        merge_sort(1,N);
        for (int i=1;i<=N;i++){
            bw.write(A[i]+"\n");
        }
        bw.flush();
        bw.close();
    }

    private static void merge_sort(int s, int e) {
        if(e-s <1) return;
        int m = s + (e-s) / 2;//중간 수 찾기
        //재귀
        merge_sort(s,m);//처음~중간 그룹
        merge_sort(m+1,e);//중간~끝 그룹
        for (int i=s;i<=e;i++){
            tmp[i] = A[i];
        }
        int k = s;
        int index1 = s;
        int index2 = m+1; 
        while (index1 <=m && index2 <=e){
            if(tmp[index1] > tmp[index2]){
                A[k] = tmp[index2]; 
                k++;
                index2++;
            } else {
                A[k] = tmp[index1];
                k++;
                index1++;
            }
        }
        while (index1 <= m){ 
            A[k] = tmp[index1];
            k++;
            index1++;
        }
        while (index2 <= e){ 
            A[k] = tmp[index2];
            k++;
            index2++;
        }
    }
}

 

---

 

N의 최대 범위가 1,000,000 이므로 O(nlogn)의 시간 복잡도로 정렬을 수행한다.

이번엔 병합 정렬의 개념을 이용해보았다.

정렬할 그룹을 최소 단위로 나누어주고, 재귀함수를 활용해 그룹 마다 병합 정렬을 수행해준다. 

각 그룹마다 첫 값, 끝 값에 각각 index1, 2를 지정하여 두 값을 1:1로 비교하고 swap 한다.

 and plus 하여 옆 그룹과 병합한다. (정렬 된 그룹들끼리 합치는 것이 plus)

합치면서 값 정렬이 또 일어난다.

 

<합치는 법>
각 그룹마다 첫 값에 각각 index 1,2를 지정하여 두 값을 비교한 후
더 작은 수를 선택해 tmp 배열에 저장하고, 선택된 인덱스를 ++ 

비교가 끝나면 남은 값 쭉 저장하고 정리!

 

 

요걸 반복해주면 된다.