[백준/BOJ] 24060번 알고리즘 수업 - 병합 정렬 1 (C/C++)

백준 온라인 저지(BOJ) 24060번 알고리즘 수업 - 병합 정렬 1 

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

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

* 사용언어 : C언어, C++

 

1. 문제

배열 A 에 서로 다른 수를 Merge Sort 로 정렬

배열 A 의 K 번째로 저장되는 수를 출력

 

- 배열 A 의 크기 N [5 ~ 500,000]

- 배열 A 의 각 원소 (중복 X) [1 ~ 1,000,000,000]

- 저장 횟수 K [1 ~ 100,000,000]

 

2. 풀이

문제에 제시된 pseudo code는 일반적인 형태의 Merge Sort입니다.

주어진 pseudo code 등으로 Merge Sort를 학습한 뒤 코딩하면 됩니다.

 

단, 주어진 내용에는 K번째 숫자를 확인하는 내용이 없기 때문에

K번째 숫자를 확인하기 위해 마지막 부분에 일부 코드를 추가했습니다. ('#결과를 A[p..r]에 저장' 부분)

 

cnt 변수를 전역으로 선언해두고, 배열에 값이 저장할 때마다 1씩 증가시켰습니다.

이 값이 K와 같아지면 해당 값을 저장하여 출력했습니다.

 

Merge Sort 시 발생하는 저장 횟수가 K보다 작으면 -1을 출력해야하기 때문에

Merge Sort 전에 res 를 -1로 초기화해두고 정렬 후에는 그대로 출력했습니다.

 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
24060_알고리즘 수업 - 병합 정렬 1
https://www.acmicpc.net/problem/24060
*/
#include <cstdio>

const int LM = 500000;
int a[LM + 5], t[LM + 5], N, K, cnt, res;

void mSort(int s, int e) {
	if (s >= e) return;

	int m = (s + e) / 2;
	mSort(s, m);
	mSort(m + 1, e);

	int i = s, j = m + 1, k = s;
	while (i <= m && j <= e) {
		if (a[i] <= a[j]) t[k++] = a[i++];
		else t[k++] = a[j++];
	}

	while (i <= m) t[k++] = a[i++];
	while (j <= e) t[k++] = a[j++];

	for (i = s; i <= e; ++i) {
		a[i] = t[i];
		if (++cnt == K) res = a[i];
	}
}

int main(){
#ifdef _WIN32
	freopen("24060.txt", "r", stdin);
#endif // _WIN32
	scanf("%d %d", &N, &K);
	for (int i = 0; i < N; ++i) scanf("%d", &a[i]);

	res = -1;
	mSort(0, N - 1);

	printf("%d\n", res);
	return 0;
}

* int 형 변수의 범위는 약 -21억 ~ 21억이므로, 문제의 숫자 범위(10억 이하)를 모두 커버할 수 있습니다.