11728번

11728번 - 배열 합치기

병합 정렬을 이용해서 문제를 풀었다.

병합 정렬 개념만 알고 코드를 어떻게 구현할 지 몰랐는데, 다시 알아보면서 코드를 짜보았다.

물론 처음에 짜지 못했다.

병합 정렬에 나오는 재귀 함수 부분에서 또 약간 헷갈렸지만, 재귀함수는 생각하고 생각할 수록.. 

생각이 재귀에 빠질 수록 힘든 것 같다.

그냥 그 코드에 적혀 있는 그대로를 곧 바로 이해하려고 노력해야겠다.

계속 재귀에 빠지다 보면 내가 다 헤어나올 수 없다.

이 문제는 모든 값들을 배열 A에 입력받고, A를 왼쪽 분할하고 정렬, 오른쪽 분할하고 정렬, 마지막으로 전체 정렬하는 방식으로 하였다.

merege() 함수에서는 while 문 세개를 통해서 tmp 라는 임시배열에 값들을 정렬하여 저장하였고,

tmp 배열을 인덱스에 맞게 A 배열에 다시 저장하는 방식으로 코딩하였다.

다양한 sort 함수는 코딩하는 법을 알고 있어야 할 것 같다. 다시 한번 풀어보기!

<정답 코드>

#include<iostream>
 
using namespace std;
int A[2000001];
int tmp[2000001];
void merge(int start, int end)
{
    int mid = (start + end) / 2;
    int left = start;
    int right = mid + 1;
    int temp_i = 0;
 
    while(left<=mid && right<=end)
    {
        if (A[left] <= A[right])
        {
            tmp[temp_i] = A[left];
            left += 1;
            temp_i += 1;
        }
        else
        {
            tmp[temp_i] = A[right];
            right += 1;
            temp_i += 1;
        }
    }
 
    while (left <= mid)
    {
        tmp[temp_i] = A[left];
        left += 1;
        temp_i += 1;
    }
 
    while (right <= end)
    {
        tmp[temp_i] = A[right];
        right += 1;
        temp_i += 1;
    }
 
    for (int i = start; i <= end; i++)
    {
        A[i] = tmp[i - start ];
    }
 
    return;
 
}
void mergesort(int start, int end)
{
    if (start == end)
    {
        return;
    }
 
    int mid = (start + end) / 2;
 
    mergesort(start, mid);
    mergesort(mid + 1, end);
    merge(start, end);
}
int main()
{
    int N, M;
    cin >> N >> M;
    for (int i = 0; i < N; i++)
    {
        cin >> A[i];
    }
    for (int i = 0; i < M; i++)
    {
        cin >> A[i+N];
    }
    int start = 0;
    int end = N + M - 1;
    mergesort(start,end);
 
    for (int i = 0; i <= N + M - 1; i++)
    {
        cout << A[i] << " ";
    }
 
}