백준 2751 수 정렬하기2

문제

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

입력

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

출력

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

예제 입력 1

5
5
4
3
2
1

예제 출력 1

1
2
3
4
5

풀이

public class Q2751_수정렬하기2 {
    public static int[] arr;
    public static int[] tmp;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        // 정렬할 배열
        arr = new int[n+1];
        // 임시 배열
        tmp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            arr[i] = sc.nextInt();
        }
        merge(1, n);
        StringBuffer sb = new StringBuffer();
        for (int i = 1; i <= n; i++) {
            sb.append(arr[i] + "\n");
        }
        System.out.println(sb.toString());
    }

    public static void merge(int s, int e) {
        // 각 구간의 길이가 1보다 작거나 같으면 이미 해당 구간은 정렬이 완료된 상태이므로 return수행
        // 최소 길이인 1까지 배열이 분리되었다면 return이 수행되어 직전 재귀함수로 돌아가고,
        // 구간의 길이는 2가 됨
        if (e - s < 1) {
            return;
        }
        // (e - s) / 2를 통해 점점 작아지는 구간의 중간값을 구하고
        // s를 더해줌으로 각 구간의 중간값 위치를 찾아줌
        int m = s + (e - s) / 2;
        // 먼저 배열을 최소단위로 쪼개줘야 하므로 재귀호출을 통해 배열을 쪼개줌
        merge(s, m);
        merge(m + 1, e);
        // 각 재귀호출에서 정렬을 위해 각 구간의 값을 임시 배열에 저장
        for (int i = s; i <= e; i++) {
            tmp[i] = arr[i];
        }
        // 각 구간의 시작지점부터 1씩 증가할 idx값
        int k = s;
        // 첫 구간의 시작idx
        int idx1 = s;
        // 두 번째 구간의 시작 idx
        int idx2 = m + 1;
        // 어느 한 구간의 정렬이 끝날 때까지 정렬 수행
        while (idx1 <= m && idx2 <= e) {
            if (tmp[idx1] > tmp[idx2]) {
                arr[k] = tmp[idx2];
                k++;
                idx2++;
            } else {
                arr[k] = tmp[idx1];
                k++;
                idx1++;
            }
        }
        // 각 그룹에 남아있는 값을 정리
        while (idx1 <= m) {
            arr[k] = tmp[idx1];
            k++;
            idx1++;
        }
        while (idx2 <= e) {
            arr[k] = tmp[idx2];
            k++;
            idx2++;
        }
    }
}

리뷰

병합정렬을 이용해 풀어야하는 알고리즘이었다.

1. 각 배열을 최소단위로 쪼개야 하므로 재귀호출을 통해 배열의 길이를 절반씩 나눠 재귀호출을 한다.
2. 재귀호출을 통해 쪼개진 각 구간의 길이가 1이 된다면 따로 정렬할 필요가 없는 상태로 return으로 해당 재귀함수를 빠져나온다.
   • 이를 통해 각 구간의 길이는 2가 되고, idx1=1, idx2=2, m = 1이 된다.
3. 두 개의 구간중에 하나의 구간 정렬이 끝날 때까지 반복문을 통해 정렬을 수행한다.
   • idx1=1, idx2=2, m = 1인 상황에서 더 작은 값이 먼저 정렬이 이뤄진다.
     idx1 > idx2라고 하면 idx=2가 되고 반복문을 빠져나온다.
     이후 각 반복문에서 나머지 값을 배열에 저장하고 해당 재귀함수를 빠져나온다.
4. 이게 각 구간의 길이는 4가 되고 3번의 과정을 다시 거친다.

병합정렬은 투포인터와 재귀함수 개념이 필요한 알고리즘이었다. 재귀함수 싫다ㅜㅜ 너무 헷갈려
여기서 헷갈렸던게, 최소단위에서 투포인터의 개념을 적용해 정렬을 하고 병합하는 구간의 크기를 키워 나가야하는데, 이걸 어떻게 구현하느냐였다.
이 문제는 재귀호출을 통해 구간의 크기를 절반씩 줄여가고, 최소 단위에 도달했을때 return을 통해 해당 재귀호출을 빠져나오며 정렬을 수행하여 문제를 해결하였다. 코딩테스트에서도 그렇고 여러 문제에서 응용된다고 하니 확실하게 숙지하고 가자!!!