[BOJ] [JAVA] 24060번 알고리즘 수업 - 병합 정렬 1

24060번: 알고리즘 수업 - 병합 정렬 1

세시간은 걸린거같다,,,

후,,,

병합 정렬 개념은 나중에 다시 적어야겠다.

여기서는 이 문제 코드만 적어야징

import java.util.*;

public class Main {
	static int[] A;
	static int[] tmp;
	static int cnt = 0;
	static int m;
	static int result = -1;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();
		m = sc.nextInt();
		A = new int[n];
		tmp = new int[n];
		for (int i = 0; i < n; i++) {
			A[i] = sc.nextInt();
			tmp[i] = A[i];
		}
		merge_sort(A, 0, n - 1);
		System.out.println(result);

	}
	static void merge_sort(int[] A, int p, int r) {
		if (p < r) {
			int q = (p + r) / 2;
			merge_sort(A, p, q); // 오른쪽 정렬
			merge_sort(A, q + 1, r); // 왼쪽 정렬
			merge(A, p, q, r); // 합치면서 정렬
		}
	}
	static void merge(int[] A, int p, int q, int r) {
		int i = p;
		int j = q + 1;
		int idx = p;
		while(i <= q && j <= r) {
			if (A[i] >= A[j]) {
				tmp[idx] = A[j];
				j++;
			} else {
				tmp[idx] = A[i];
				i++;
			}
			idx++;
		}
		while (i <= q) {
			tmp[idx] = A[i];
			i++;
			idx++;
		}
		while (j <= r) {
			tmp[idx] = A[j];
			j++;
			idx++;
		}
		for (int k = p; k <= r; k++) {
			cnt++;
			if (cnt == m) {
				result = tmp[k];
				return;
			}
			A[k] = tmp[k];
		}
	}

}

병합 정렬은 배열의 가운데를 중심으로 오른쪽과 왼쪽으로 나누어 각각 정렬한 후 다시 합치며 정렬한다.

이미 정렬된 오른쪽 배열과 왼쪽 배열을 합치며 정렬하기 때문에

병합 시에는 두 배열의 index 순서대로 비교하며 정렬할 수 있다.

이 문제에서의 추가 조건을 이해하는 것이 어려웠는데, 노트에 쓰면서 해보니깐 이해가 되더라,, ㅋㅋ

// m번째 실행되었을 때 배열에 정렬되는 수를 찾는 코드
for (int k = p; k <= r; k++) {
			cnt++;
			if (cnt == m) {
				result = tmp[k];
				return;
			}
			A[k] = tmp[k];
		}

위 코드를 계속 k=0으로 시작해버려서 시간이 오래걸렸다!