[Baekjoon] 24260번: 알고리즘 수업 - 병합 정렬 1

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

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

 

---

 

문제 해결 과정

착안

문제에서 주어진 합병 정렬(병합 정렬, merge sort) 의사 코드를 그대로 구현하여 문제를 해결하였다.

 

구현

알고리즘의 의사 코드를 그대로 제공하여 편리하게 구현할 수 있었다. 처음에는 중간 결과를 합치는 merge 함수에서 사용되는 tmp 배열을 크기에 맞게 계속 할당/해제하는 방식으로 구현했는데, tmp 배열을 아예 최초의 배열 A를 생성할 때 같은 크기로 할당해서 이용하는 방식으로 변경하였다.

 

또한, 실행 속도를 높여보기 위해 문제에서 찾고자 하는 수를 찾았을 경우 정렬을 더이상 수행하지 않고 return 하도록 코드를 추가해보았다(문제의 제 1 목적이 정렬이 아니므로). 쉽게 예상할 수 있는 부분으로, merge 함수의 실행 시간이 오래 걸리므로 merge 함수의 실행을 제어하면 실행 속도를 눈에 띠게 단축시킬 수 있다(아래의 실행 결과 참고).

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>

using namespace std;

int K;
int* tmp;

void merge(int* A, int p, int q, int r)
{
	int i = p;
	int j = q + 1;
	int t = 0;
	while (i <= q and j <= r)
	{
		if (A[i] <= A[j])
			tmp[t++] = A[i++];
		else
			tmp[t++] = A[j++];
	}

	while (i <= q)
		tmp[t++] = A[i++];

	while (j <= r)
		tmp[t++] = A[j++];

	i = p;
	t = 0;
	while (i <= r)
	{
		A[i++] = tmp[t++];
		if (!--K)
		{
			cout << A[i - 1];
			return;
		}
	}
}

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);
		if (!K) return;
		merge(A, p, q, r);
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int N;
	cin >> N >> K;

	int* A = new int[N];
	tmp = new int[N];

	for (int i = 0; i < N; i++)
		cin >> A[i];

	merge_sort(A, 0, N - 1);
	if (K > 0) cout << "-1\n";

	delete[] A;
	delete[] tmp;
	return 0;
}

 

실행 결과

아래 코드부터 순서대로

1. tmp 배열의 동적 메모리 할당을 merge 함수 내에서 빈번하게 수행
2. tmp 배열의 동적 메모리 할당을 최초 1회만 수행하고 재활용
3. merge 함수 실행 앞부분 return 코드 추가
4. merge_sort 함수(오른쪽) 실행 앞부분 return 코드 추가

를 통한 실행 결과이다.