[백준] 2751 - 수 정렬하기2 (자바/JAVA): 합병 정렬(Merge Sort)

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

문제

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

입력

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

출력

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

---

처음에 선택 정렬을 썼다가 시간 초과가 나서 합병 정렬을 사용했는데도 시간 초과가 났다.

그래서 Scanner를 BufferedReader로, sysout println을 BufferedWriter로 바꿨는데도 시간 초과가 났다.

 

정렬 자체에 문제가 있는 것 같아서 질문을 찾아보다가 문제를 발견했다 하하

https://www.acmicpc.net/board/view/31887

병합 정렬을 할 때, merge를 수행할 때마다 배열의 전체 크기, 혹은 right만큼을 할당하고 해제하기를 반복하면 안 됩니다. 크기가 N인 메모리를 할당하는 것은 O(N) 시간이 걸리고, merge가 O(N)번 호출되기 때문에 총 시간복잡도가 O(N^2)이 됩니다. 이를 해결하기 위한 방법으로는,

1. 복사를 하기 위한 큰 배열 하나를 미리 할당해두고 계속 사용
2. merge가 담당하는 구간의 크기(right - left + 1)만큼만 메모리를 할당 등이 있습니다.

merge를 할 때마다 새로운 배열 tmp를 전체 배열의 크기인 arr.length만큼 만들어주니까 메모리 할당에 시간이 걸린 것이다.

그래서 입력의 최대 크기인 100만으로 sorted 배열을 static 변수로 선언하고, 이 배열을 계속 사용해서 메모리를 아꼈다.

결과는 성공~_~ 

 

package BOJ0726;

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

public class BOJ_2751_수정렬2 {
	static int[] sorted = new int[1000001];

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[] arr = new int[N];
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}

		// merge sort
		mergeSort(arr, 0, N - 1);

		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		for (int i = 0; i < arr.length; i++) {
			bw.write(Integer.toString(arr[i]) + "\n");

		}
		bw.close();

	}

	static int[] merge(int[] arr, int l, int mid, int r) {
		int i = l; // 왼쪽 배열의 시작 index
		int j = mid + 1; // 오른쪽 배열의 시작 index
		int k = l; // merge 결과 배열의 index

		while (i <= mid && j <= r) {
			if (arr[i] <= arr[j]) {
				sorted[k++] = arr[i++];
			} else {
				sorted[k++] = arr[j++];
			}
		}

		if (i > mid) {
			for (int right = j; right <= r; right++) {
				sorted[k++] = arr[right];
			}
		} else {
			for (int left = i; left <= mid; left++) {
				sorted[k++] = arr[left];
			}
		}

		// 원래 배열에 복사
		for (int tmp = l; tmp <= r; tmp++) {
			arr[tmp] = sorted[tmp];
		}

		return arr;

	}

	static int[] mergeSort(int[] arr, int l, int r) {
		int mid;
		if (arr.length == 1) {
			return arr;
		}

		if (l < r) {
			mid = (l + r) / 2;
			arr = mergeSort(arr, l, mid);
			arr = mergeSort(arr, mid + 1, r);
			arr = merge(arr, l, mid, r);
		}

		return arr;
	}

}