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

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

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

 

 

 

[풀이 후기]
난이도 : ★☆☆☆ (Beginner)
문제 종류 : Sort
해결 방법 : Merge Sort

 

 

* 난이도 구분
★☆☆☆ (Beginner) : 알고리즘 적용만으로 해결 가능
★★☆☆ (Advanced) : 알고리즘을 활용하여 구현해야 해결 가능
★★★☆ (Pro) : 알고리즘을 활용한 구현 + 최적화 아이디어로 해결 가능
★★★★ (Expert) : Pro보다 발전된 최적화 아이디어로 해결 가능

 

---

문제

 

문제 분석

1. N = 최대 50만, K = 최대 1억, A = 최대 10억 이므로, 모두 int형 변수로 선언이 가능하다. 
2. Merge Sort를 구현하자. 
3. K번째 저장되는 수를 출력해야하므로, 어떤 값을 출력해야하는지 생각해보자. 

 

Merge Sort의 원리는 아래 포스팅을 참고하세요 :)

[자료구조][정렬][C/C++] Merge Sort (병합정렬)

[자료구조][정렬][C/C++] Merge Sort (병합정렬)

 

 

---

 

접근 방법

 

배열 A에 K번째 저장되는 수가 무슨 뜻인지 아래 예시를 통해서 확인해 보자. 

 

위 배열을 Merge Sort 한다면, 중간 지점을 구해서, 좌우로 나누어 Sorting 하게 된다. 

1. mid = (1 + 5) / 2 = 3 → mergeSort(1, 3), mergeSort(4, 5)
2. mid = (1 + 3) / 2 = 2 → mergeSort(1, 2), mergeSort(3, 3)

mergeSort(1, 2) 에서는 1번 Index와 2번 Index의 값을 비교해서, 둘 중에 작은 수인 4를 A 배열에 copy한다. 

따라서, A 배열에 1번째로 저장되는 수는 4 이다. 

 

다음으로는 5가 copy 되므로, A 배열에 2번째로 저장되는 수는 5 이다. 

K=2까지 결정된, Merge Sort 결과

 

 

mergeSort(3, 3)은 시작과 끝이 같은 구간이니, 패스 한다. 

mergeSort(1, 3) 에서는 1번 Index와 3번 Index의 값을 비교해서, 둘 중에 작은 수인 1을 A 배열에 copy한다. 

따라서, A 배열에 3번째로 저장되는 수는 1 이다. 

 

다음으로는 4가 copy 되므로, A 배열에 4번째로 저장되는 수는 4 이다. 

다음으로는 5가 copy 되므로, A 배열에 5번째로 저장되는 수는 5 이다. 

K=5까지 결정된, Merge Sort 결과

 

이런식으로  A 배열에 K번째로 저장되는 수가 정해지게 된다.

 

"배열 A에 K번째 저장되는 수"는
"배열 A에 K번째로 copy되는 수" 이다. 

 

이제 merge Sort 코드를 살펴보자. 

아래와 같이 copy 부분에 cnt변수를 두어서, 몇 번째로 저장되는 수인지 check 할 수 있다. 

int N, K, cnt;
int A[LM + 5], trr[LM + 5], ans;

void mergeSort(int s, int e) {
	if (s >= e) return;		// 1. base condition

	int mid = (s + e) / 2;		// 2. divide & conquer
	mergeSort(s, mid);
	mergeSort(mid + 1, e);

	int i = s, j = mid + 1, k = s;		// 3. merge
	while (i <= mid && j <= e) {
		if (A[i] <= A[j]) trr[k++] = A[i++];
		else trr[k++] = A[j++];
	}
	while (i <= mid) trr[k++] = A[i++];
	while (j <= e) trr[k++] = A[j++];

	for (i = s; i <= e; i++) {	// 4. copy
		A[i] = trr[i];

		if (++cnt == K) {	// cnt : 현재 몇 번째 저장되는 수 인지 Check
			ans = A[i];	// K번째에 도달한 경우, 정답을 저장한다. 
		}
	}
}

 

 

그런데, K번째로 copy되는 수를 구하고 나서는 더이상 Merge Sort를 진행할 필요가 없으므로, 

중간에 그만둘 수 있도록 아래처럼 코드를 만들면 속도를 개선할 수 있다. (이것을 pruning == 가지치기 이라고 한다. )

int N, K, cnt;
int A[LM + 5], trr[LM + 5], ans;

void mergeSort(int s, int e) {
	if (s >= e) return;		// 1. base condition

	int mid = (s + e) / 2;		// 2. divide & conquer
	mergeSort(s, mid);
	mergeSort(mid + 1, e);

	if (cnt >= K) return;	// pruning

	int i = s, j = mid + 1, k = s;		// 3. merge
	while (i <= mid && j <= e) {
		if (A[i] <= A[j]) trr[k++] = A[i++];
		else trr[k++] = A[j++];
	}
	while (i <= mid) trr[k++] = A[i++];
	while (j <= e) trr[k++] = A[j++];

	for (i = s; i <= e; i++) {	// 4. copy
		A[i] = trr[i];

		if (++cnt == K) {	// cnt : 현재 몇 번째 저장되는 수 인지 Check
			ans = A[i];	// K번째에 도달한 경우, 정답을 저장한다. 
			break;		// copy 종료, pruning
		}
	}
}

 

 

이제 main 함수를 포함한 코드를 살펴보자. 

#include <stdio.h>

const int LM = 500'000;
int N, K, cnt;
int A[LM + 5], trr[LM + 5], ans;

void mergeSort(int s, int e) {
	if (s >= e) return;		// 1. base condition

	int mid = (s + e) / 2;		// 2. divide & conquer
	mergeSort(s, mid);
	mergeSort(mid + 1, e);

	if (cnt >= K) return;	// pruning

	int i = s, j = mid + 1, k = s;		// 3. merge
	while (i <= mid && j <= e) {
		if (A[i] <= A[j]) trr[k++] = A[i++];
		else trr[k++] = A[j++];
	}
	while (i <= mid) trr[k++] = A[i++];
	while (j <= e) trr[k++] = A[j++];

	for (i = s; i <= e; i++) {	// 4. copy
		A[i] = trr[i];

		if (++cnt == K) {	// cnt : 현재 몇 번째 저장되는 수 인지 Check
			ans = A[i];	// K번째에 도달한 경우, 정답을 저장한다. 
			break;		// copy 종료, pruning
		}
	}
}

int main() {
	ans = 0;
	scanf("%d %d", &N, &K);
	for (int i = 1; i <= N; i++) {
		scanf("%d", A + i);
	}

	mergeSort(1, N);
	if (cnt < K) printf("-1\n");	// mergeSort 종료 후에도 K번째에 도달하지 못하면 -1
	else printf("%d\n", ans);	// K번째로 copy된 수 출력

	return 0;
}

 

---

제출 결과