[백준] 24060번 : 알고리즘 수업 - 병합 정렬 1

문제

 

 

접근 방식

Merge Sort를 구현하여 k번째로 정렬되는 수를 구하면 된다.

정렬 후에 k번째 수를 구하는 것이 아닌 정렬 과정에서의 k번째 수인 것에 유의해야 한다.

 

문제에서 요구하는 구현 방식은 바텀업이 아닌 탑다운 방식이기 때문에

주어진 의사코드대로 구현하면서 카운팅을 해주다 k번째일 때 수를 기록만 하면 된다.

 

바텀업 방식은 정렬 순서가 조금 다르기 때문에 정렬 결과는 같더라도

해당 문제를 풀기에는 적합하지 않다.

 

우선 0번째 인덱스부터 n-1번째 인덱스를 정렬하기 위해서는

왼쪽과 오른쪽 절반으로 나누어가면서 더 이상 나눌 수 없을 때까지 나눈 후에

다시 배열을 합쳐가면서 더 작은 값들을 임시 배열에 기록한 후에

임시 배열의 결과를 원본 배열에 옮겨주면 된다.

 

풀이

public class Main {

	static int cnt = 0, k, result = -1;
	static int[] arr, tmp;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int n = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());

		arr = new int[n];
		tmp = new int[n];

		st = new StringTokenizer(br.readLine());

		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		sort(0, n - 1);

		System.out.println(result);
	}

	static void sort(int start, int end) {
		if (cnt == k) return;
		if (start < end) {
			int mid = (start + end) / 2;

			sort(start, mid);
			sort(mid + 1, end);
			merge(start, mid, end);
		}
	}

	static void merge(int start, int mid, int end) {
		int i = start;
		int j = mid + 1;
		int idx = 0;

		while (i <= mid && j <= end) {
			if (arr[i] <= arr[j]) tmp[idx++] = arr[i++];
			else tmp[idx++] = arr[j++];
		}

		while (i <= mid) tmp[idx++] = arr[i++];
		while (j <= end) tmp[idx++] = arr[j++];

		i = start;
		idx = 0;

		while (i <= end) {
			cnt++;

			if (cnt == k) {
				result = tmp[idx];
				break;
			}

			arr[i++] = tmp[idx++];
		}
	}
}