문제
오늘도 서준이는 병합 정렬 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.
N개의 서로 다른 양의 정수가 저장된 배열 A가 있다. 병합 정렬로 배열 A를 오름차순 정렬할 경우 배열 A에 K 번째 저장되는 수를 구해서 우리 서준이를 도와주자.
크기가 N인 배열에 대한 병합 정렬 의사 코드는 다음과 같다.
merge_sort(A[p..r]) { # A[p..r]을 오름차순 정렬한다.
if (p < r) then {
q <- ⌊(p + r) / 2⌋; # q는 p, r의 중간 지점
merge_sort(A, p, q); # 전반부 정렬
merge_sort(A, q + 1, r); # 후반부 정렬
merge(A, p, q, r); # 병합
}
}
# A[p..q]와 A[q+1..r]을 병합하여 A[p..r]을 오름차순 정렬된 상태로 만든다.
# A[p..q]와 A[q+1..r]은 이미 오름차순으로 정렬되어 있다.
merge(A[], p, q, r) {
i <- p; j <- q + 1; t <- 1;
while (i ≤ q and j ≤ r) {
if (A[i] ≤ A[j])
then tmp[t++] <- A[i++]; # tmp[t] <- A[i]; t++; i++;
else tmp[t++] <- A[j++]; # tmp[t] <- A[j]; t++; j++;
}
while (i ≤ q) # 왼쪽 배열 부분이 남은 경우
tmp[t++] <- A[i++];
while (j ≤ r) # 오른쪽 배열 부분이 남은 경우
tmp[t++] <- A[j++];
i <- p; t <- 1;
while (i ≤ r) # 결과를 A[p..r]에 저장
A[i++] <- tmp[t++];
}입력
첫째 줄에 배열 A의 크기 N(5 ≤ N ≤ 500,000), 저장 횟수 K(1 ≤ K ≤ 108)가 주어진다.
다음 줄에 서로 다른 배열 A의 원소 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 109)
출력
배열 A에 K 번째 저장 되는 수를 출력한다. 저장 횟수가 K 보다 작으면 -1을 출력한다.
예제 입력 1
5 7
4 5 1 3 2
예제 출력 1
3
4 5 1 3 2 -> 4 5 1 3 2 -> 4 5 1 3 2 -> 1 5 1 3 2 -> 1 4 1 3 2 -> 1 4 5 3 2 -> 1 4 5 2 2 -> 1 4 5 2 3 -> 1 4 5 2 3 -> 1 2 5 2 3 -> 1 2 3 2 3 -> 1 2 3 4 3 -> 1 2 3 4 5. 총 12회 저장이 발생하고 일곱 번째 저장되는 수는 3이다.
예제 입력 2
5 13
4 5 1 3 2
예제 출력 2
-1
저장 횟수 12가 K 보다 작으므로 -1을 출력한다.
풀이
병합 정렬을 재귀로 구현하고 어떤 숫자가 몇 번째에 정렬되는지를 기록해야 하는 문제였다.
의사코드가 나와있어서 사실 그대로 작성하면 되는데 병합 정렬의 원리를 공부하는 데 시간을 썼다.
MSort 함수 안에서 MSort 자신을 재귀적으로 호출하면서 배열을 계속해 반으로 쪼개나가고, 실제로 정렬이 되면서 합치는 과정은 Merge 함수 안에서 일어난다.
array는 처음에 입력으로 들어온 숫자들을 받기 위한 배열이다.
sorted는 Merge에서 쪼개진 배열을 정렬할 때 사용하는 임시 배열이다.
using System;
using System.Collections.Generic;
using System.Linq;
namespace Baekjoon
{
class Program
{
static void Main(string[] args)
{
int[] inputs = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
int[] array = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
int k = inputs[1];
int[] sorted = new int[inputs[0]]; // sorted array
List<int> saveNums = new List<int>();
MSort(array, 0, array.Length - 1);
if (saveNums.Count < k)
{
Console.WriteLine(-1);
}
else
{
Console.WriteLine(saveNums[k-1]);
}
void MSort(int[] arr, int start, int end)
{
// split
if (start < end)
{
int mid = (start+end) / 2; // 그냥 end / 2 하면 mid가 뒤로 전진하기 못해서 무한루프 돌게 됨
MSort(arr, start, mid);
MSort(arr, mid + 1, end);
Merge(arr, start, mid, end);
}
}
void Merge(int[] arr, int start, int mid, int end)
{
int i = start;
int j = mid + 1;
int t = start; // index of sorted array
// mid 기준 앞쪽과 뒤쪽 배열 원소 중 작은 것을 sorted의 앞쪽부터 채운다.
while (i <= mid && j <= end)
{
if (arr[i] <= arr[j])
{
sorted[t++] = arr[i++];
}
else
{
sorted[t++] = arr[j++];
}
}
// 쪼개진 배열 중 하나가 먼저 모든 원소를 소진했을 경우
if (i > mid)
{
// 앞쪽이 먼저 끝난 경우
// 뒤쪽에서 나머지 그대로 sorted에 복사
for (int l = j; l <= end; l++)
{
sorted[t++] = arr[l];
}
}
else
{
// 뒤쪽이 먼저 끝난 경우
// 앞쪽에서 나머지 그대로 sorted에 복사
for (int l = i; l <= mid; l++)
{
sorted[t++] = arr[l];
}
}
for (int l = start; l <= end; l++)
{
saveNums.Add(sorted[l]);
arr[l] = sorted[l]; // copy sorted array to original array
}
}
}
}
}
Main()
- int[] inputs에 배열 길이와 저장 순번을 받는다.
- array에 입력 배열을 받는다.
- 임시 배열 sorted를 array와 같은 크기로 생성한다.
- 병합 정렬 과정에서 변경되는 (저장되는) 숫자를 담을 리스트 saveNums를 만든다.
- MSort(배열, 시작 index, 끝 index);를 호출한다.
- 저장되는 숫자를 담은 saveNums의 길이가 k보다 작으면 k번째 저장 수가 없는 것이므로 -1을 호출하고, 저장되는 숫자가 k개 이상이었다면 k번째 저장수를 saveNums[k-1];로 찾는다.
MSort(쪼갤 배열, 시작 index, 끝 index)
배열을 절반으로 쪼개고, 쪼갠 것들을 합치면서 정렬하는 Merge()를 호출하는 함수이다.
- 시작 index가 끝 index보다 작을 때만 아래의 코드를 수행한다. 시작 index가 끝 index와 같아진다는 것은 배열의 길이가 1인, 하나의 원소 단위까지 쪼개진 것이기 때문이다. (배열 길이가 2면 start 0, end 1일 것이다.)
- 배열의 중간 지점 index를 (시작 index + 끝 index) / 2로 계산한다.
주의) 단순히 end/2를 하게 되면... 나중에 mid+1 값이 증가하지 않아서 무한루프를 도는 대참사가 일어난다. 어떻게 아냐고? 내가 그랬다... - 배열을 쪼갠다. 이 과정이 재귀를 통해 일어난다. 시작~중간 index를 반으로 쪼개는 MSort()와 중간~끝 index를 반으로 쪼개는 MSort()를 MSort() 안에서 호출한다.
- 쪼갠 배열을 합치는 (그러면서 정렬하는) Merge()를 수행한다.
Merge(정렬해야 할 배열, 시작 index, 중간 index, 끝 index)
받은 배열을 중간 index 기준으로 앞, 뒤로 나누어 원소를 하나씩 비교하며 정렬된 상태로 만든다.
- i는 시작 index, j는 mid+1로 받아 중간 기준 앞, 뒤 배열의 가장 첫 원소에 접근할 수 있도록 준비한다.
- t는 정렬된 배열을 만들기 위해 sorted의 각 자리에 접근하기 위한 index이다. 일단 start로 받아둔다.
- i가 mid보다 작거나 같고, j가 end보다 작거나 같은지 확인해 앞, 뒤 배열 모두에 원소가 하나 이상 남아있을 때 양쪽 배열의 원소 크기 비교를 진행한다. 한쪽이라도 배열의 원소를 모두 소진하면 비교할 필요가 없기 때문이다.
- arr[i] 앞쪽 배열의 원소와 arra[j] 뒤쪽 배열의 원소 중 작은 쪽이 sorted[t] 자리에 들어간다. 이후 i와 j 둘 중 하나의 index를 증가시켜 다음 원소와 비교할 수 있게 준비해두고, t 역시 index를 하나 증가시켜 다음 자리에 접근할 수 있도록 준비한다.
- 4번 과정을 반복하다보면, 앞쪽이나 뒤쪽 배열 중 더 이상 정렬할 원소가 없게 되는 경우가 생긴다. 즉, i > mid이거나 j > end가 되면 중간 기준 앞쪽이나 뒤쪽 배열 중 하나의 원소를 모두 사용했다는 뜻이다. 이때는 양쪽 배열의 원소 값의 크기를 비교하는 작업을 멈추고, 두 배열 중 남은 원소가 있는 배열을 sorted에 그대로 하나씩 index를 증가시켜가며 자리에 넣어준다.
- 정렬한 index 범위가 start부터 end까지이므로 그 범위동안 for문을 돌면서 sorted 배열에 들어있는 수를 saveNums에 추가하고, 본래 배열에서도 sorted에 들어있는 순서대로 정렬한다.
MSort()의 호출 과정이 헷갈릴 수 있다. 헷갈리면 우리에겐 Visual Studio의 F11이 있다. 한줄 한줄 실행해가면서 흐름을 따라가면 된다.
예제 입력 1의 [4,5,1,3,2] 배열이 들어온다고 가정해보자.
- MSort([4,5,1,3,2], 0, 4)를 수행한다.
- 0<4 이므로 mid = (0+4)/2 = 2이다.
- MSort([4,5,1], 0, 2)를 수행한다. (MSort([3,2], 3,4); Merge(array, 0, 4); 남겨둔 상태)
- 0<2 이므로 mid = 1이다.
- MSort([4,5], 0, 1)를 수행한다. (MSort([1], 2, 2); Merge([4,5,1], 0, 2); 남겨둔 상태)
- 0<1 이므로 mid = 1/2 = 0이다.
- MSort([4], 0, 0)를 수행한다. (MSort([5], 1, 1); Merge([4,5], 0,1); 남겨둔 상태)
- 0<0 성립하지 않으므로 MSort([4], 0, 0);은 끝나고 7번에서 남겨둔 MSort([5], 1,1);를 수행한다.
- 1<1 성립하지 않으므로 MSort([5], 1,1);은 끝나고 7번에서 남겨둔 Merge([4,5], 0,1);를 수행한다.
- i는 중간 기준 앞쪽 배열의 가장 앞 index, j는 중간 기준 뒤쪽 배열의 가장 앞 index이다. 따라서 Merge([4,5], 0, 0, 1)를 수행할 때 앞쪽 배열은 [4], 뒤쪽 배열은 [5]이며 mid = 0, i = 0, j = 1이다.
- while loop에서 arr[0] < arr[1] 이므로 sorted[0]에는 arr[0], 4가 먼저 들어가고, t와 i를 모두 1씩 증가시킨다. i가 mid보다 커져(==앞 배열의 원소를 sorted에 모두 집어넣었으니 배열이 끝나) while loop을 탈출한다.
- i가 mid보다 커졌으니 앞 배열은 모두 사용한 것으로 알고 뒷 배열 원소를 하나씩 sorted에 순서대로 넣어준다. sorted[1]=5가 된다.
- 앞 뒤 배열을 모두 sorted에 정렬해서 넣었으니 이제 정렬된 배열을 원본 배열에 복사한다. 이때 sorted 전체를 복사하는 것이 아니라 sorted의 start~end index, 즉 sorted[0]~sorted[1], 현재 정렬한 범위만 복사한다. 그리고 이 범위의 숫자만이 변경된 숫자가 된다. 그래서 saveNums에 sorted에서 현재 정렬한 숫자들을 앞에서부터 추가하는 것이다. 결국 현재 Merge에서 변경한 숫자가 우리가 나중에 알고 싶은 몇번째에 어떤 숫자가 변경되었는지이므로!
- 여기까지 하면 Merge([4,5], 0, 1)이 끝난 것이다. 다음은 5번에서 남겨둔 MSort([1], 2, 2); Merge([4,5,1], 0, 2); 이다. 앞의 과정은 원소 하나이므로 더 쪼개지 않고 리턴되어 바로 Merge([4,5,1], 0, 2);를 실행할 것이다. Merge에서 i는 0, j는 2가 되어 [4,5]가 앞 배열, [1]이 뒷 배열이 된다. 앞 단계를 충분히 이해했다면 알겠지만, Merge 안에서 뒷 배열인 1이 먼저 sorted에 들어가고 그 다음에 뒷배열에 더 이상 비교할 숫자가 없으므로 4, 5가 순서대로 sorted 배열에 들어간다. 따라서 saveNums에는 1,4,5가 추가되어 saveNums는 {4,5,1,4,5}가 된다. array는 [1,4,5,3,2]가 된다.
- 다음으로 MSort([3,2], 3,4); Merge([4,5,1,3,2], 0, 4);가 남았다. MSort([3,2] 3, 4);를 수행하면 MSort([3], 3, 3); MSort([2], 4, 4); Merge([3,2], 3, 4);를 수행해야 하며 앞의 MSort 부분은 사실상 아무것도 하지 않고 리턴하므로 결국 Merge([3,2], 3,4); 를 수행한다. 이 과정에서 원 배열 array의 index 3, 4자리가 정렬되어 array는 [1,4,5,2,3]이 되고, saveNums에 2, 3이 차례로 추가되어 saveNums는 {4,5,1,4,5,2,3}이 된다.
- 최종적으로 5번에서 남겨둔 Merge(array, 0,4);가 남았다. 현재 array는 앞뒤 각각 정렬 과정을 거쳐 {1,4,5,2,3}이며 i는 0, j는 3이다. Merge 안에서는 [1,4,5] 배열과 [2,3] 배열을 정렬하는 과정이 일어나고 이 과정에서 sorted에 1,2,3 순서로 들어간 뒤 while loop을 탈출해 앞쪽의 남은 원소 4, 5가 sorted에 마저 들어간다. 따라서 saveNums에 1,2,3,4,5가 추가되어 saveNums는 {4,5,1,4,5,2,3,1,2,3,4,5}가 되며, array는 최종적으로 [1,2,3,4,5]로 정렬된다.
처음에는 어디에서 변경 값을 받아야 할지 이해가 안 되다가, F11로 한줄씩 실행하면서 에러도 잡고 이해도 하게 됐다.
병합 정렬... 이해도 했고 외워서 비슷한 문제에 대응할 수 있게끔 해야겠다.
* 이 게시물은 카카오 데이터 센터 고장의 역경을 딛고 출간되었습니다.
'알고리즘 > 백준' 카테고리의 다른 글
| [백준] 10250 ACM 호텔 C# (0) | 2022.10.25 |
|---|---|
| [백준] 2292 벌집 C# (0) | 2022.10.25 |
| [백준 3단계] C# 15552 빠른 A+B (StringBuilder, StringReader) (1) | 2022.09.20 |
| [백준 3단계 반복문] C# 8393 합 (0) | 2022.09.20 |
| [백준 1단계] C# 2884 알람시계 (1) | 2022.09.19 |
댓글