[JAVA] 백준 2751 자바 / 병합 정렬

수 정렬하기 2

시간 제한메모리 제한제출정답맞은 사람정답 비율

2 초

256 MB

130126

34530

23507

30.029%

문제

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

 

 

 

문제풀이

 

 

이 문제를 읽고 2750과 다른 것은 무엇일까 크게 다를 것은 없지 않을까 생각했다면 경기도 오산이다.

많이 사용하는 버블정렬과 같은 것들을 썼다간 O(n2)의 시간 복잡도가 발생하여 1,000,000개가 들어왔을 때

시간 초과가 나게 된다.

 

 

따라서 이 부분에 관해서는 백준이

 

 

이 문제는 O(NlogN) 이하의 복잡도를 갖는 정렬을 사용해야 하고, 이에 해당하는 것으로는 병합 정렬, 힙 정렬 등이 있습니다. 또는 기수 정렬이나 카운팅 정렬을 사용해도 됩니다.

 

 

라고 간결하게 정리하여 말하고 있음.. 문서는 아래 참고

글 읽기 - ★☆★☆★ [필독] 수 정렬하기 2 FAQ ★☆★☆★ (acmicpc.net)

글 읽기 - ★☆★☆★ [필독] 수 정렬하기 2 FAQ ★☆★☆★

 

 

 

 

static void MergeTwoArea(int[] arr, int left, int mid, int right) {
        int fIdx = left;
        int rIdx = mid + 1;
        int sIdx = left;

        while (fIdx <= mid && rIdx <= right) {
            if (arr[fIdx] <= arr[rIdx]) {
                res[sIdx] = arr[fIdx++];
            } else {
                res[sIdx] = arr[rIdx++];
            }
            sIdx++;
        }

        if (fIdx > mid) {
            for (int i = rIdx; i <= right; i++, sIdx++) {
                res[sIdx] = arr[i];
            }
        } else {
            for (int i = fIdx; i <= mid; i++, sIdx++) {
                res[sIdx] = arr[i];
            }
        }

        for (int i = left; i <= right; i++) {
            arr[i] = res[i];
        }
    }

    static void MergeSort(int[] arr, int left, int right) {
        int mid;

        if (left < right) {
            mid = (left + right) / 2;

            MergeSort(arr, left, mid);
            MergeSort(arr, mid + 1, right);

            MergeTwoArea(arr, left, mid, right);
        }
    }

 

아직 너무 헷갈려서 일부만 작성