[백준/자바] 2751 수 정렬하기 2

[백준/자바] 2751 수 정렬하기 2

 

📌 문제 

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

 

 

⚔ 입력

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

 

 

📣 출력

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

 

 

 

---

 

 

 

💎 문제분석하기

 

간단한 정렬 문제이지만 주어지는 숫자가 어마어마하기 때문에 좋은 성능의 알고리즘이 필요하다. 

 

이 문제는 퀵정렬로 풀려고 여러번 시도를 했지만 계속해서 시간초과가 났다. 

 

병합 정렬로 풀 수 있다. 

 

 

 

 

📜 병합 정렬 이해하기 

 

 

병합 정렬을 논리적으로 이해하는 것은 어렵지 않다. 

 

https://www.programiz.com/dsa/merge-sort

 

 

하지만 이 로직이 코드에서 돌아가는 것은 이해하는데 시간이 걸렸다. 

 

로직은 divide => merge 형태이다. 

 

메인 함수에서 호출을 받은 뒤 divide를 진행하는 과정에서 top-down 방식이 많이 사용되는데 재귀적 호출 방식으로 진행된다. 

 

인텔리제이에서 디버깅 모드로 돌려보면서 간신히 이해했다. 

 

개인적으로 어려웠던 이유가 sort와 merge가 같은 반복문이 종료되지 않은 채 동시적으로 진행이 되었기 때문이다. sort가 모두 끝난 후 merge가 되는게 아니라는 점에서 헷갈리는 부분이었다. 

 

다음 코드를 돌려본다. 

 

array는 [4, 3, 2, 1]이 주어진다. 

 

 

먼저 왼쪽이 [4,3] [4] [3]으로 분해가 되고 

그 다음 오른쪽이 분해가 된 뒤 

 

병합 과정이 들어간다. 

 

 

 

 

 

 

 

 

💡 코드 구현하기

 

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

public class Main {
	public static int[] inputNumbers;
	public static int[] sortedArray;

	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());
		inputNumbers = new int[N];
		sortedArray = new int[N];

		for (int i = 0; i < N; i++) {
			inputNumbers[i] = Integer.parseInt(br.readLine());
		}

		mergeSort(0, N - 1);

		for (int i = 0; i < N; i++) {
			bw.write(inputNumbers[i] + "\n");
		}

		bw.flush();
		bw.close();
	}

	private static void mergeSort(int left, int right) {
		if (right - left < 1)
			return;
		int median = left + (right - left) / 2;

		mergeSort(left, median);
		mergeSort(median + 1, right);

		if (right + 1 - left >= 0) {		// 복사하여 새로운 배열에 넣기 
			System.arraycopy(inputNumbers, left, sortedArray, left, right + 1 - left);
		}

		merge(right, median, left);
	}

	private static void merge(int right, int median, int left) {

		int newLeft = left;
		int newRight = median + 1;

		while (newLeft <= median && newRight <= right) {

			if (sortedArray[newLeft] > sortedArray[newRight]) {
				inputNumbers[left] = sortedArray[newRight];
				left++;
				newRight++;
			} else {
				inputNumbers[left] = sortedArray[newLeft];
				left++;
				newLeft++;
			}
		}

		while (newLeft <= median) {
			inputNumbers[left] = sortedArray[newLeft];
			left++;
			newLeft++;
		}

		while (newRight <= right) {
			inputNumbers[left] = sortedArray[newRight];
			left++;
			newRight++;
		}
	}
}

 

 

 

 

 

 

 

 

 

---

 

 

 

풀이 참고 : Do it! 알고리즘 코딩테스트 - 자바 편