[11728] 배열 합치기

---

 

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

11728번: 배열 합치기

 

---

 

🔎 해결방법 

1. 배열 a와 b를 각각 입력받지 않고, 두 배열을 한번에 받을 배열 arr을 선언

2. 배열 arr의 0 ~ (n - 1) 번째 인덱스에 입력받은 배열 a의 내용 저장

3. 배열 arr의 n ~ (m - 1) 번째 인덱스에 입력받은 배열 b의 내용 저장

4. MergeSort 알고리즘 사용하여 정렬한 뒤에 그 결과를 배열 answer에 저장

 

---

 

💡 내 코드(C++)

// [11728] 배열 합치기
// https://www.acmicpc.net/problem/11728
// 분할정복

#include <cstdio>
#define MAX 10000010
using namespace std;

void sort(int start, int end);
void merge(int start, int end);
int n, m; // 배열 A의 크기, 배열 B의 크기
int arr[MAX], answer[MAX];

int main(void)
{
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    
    for (int i = n; i < n + m; i++) {
        scanf("%d", &arr[i]);
    }
    
    sort(0, n + m - 1);

    for (int i = 0; i < n + m; i++) {
        printf("%d ", answer[i]);
    }
}

void sort(int start, int end)
{
    if (start == end) {
        return;
    }
    
    int mid = (start + end) / 2;
    sort(start, mid);
    sort(mid + 1, end);
    merge(start, end);
}

void merge(int start, int end)
{
    int mid = (start + end) / 2;
    int i = start, j = mid + 1, k = 0;
    
    while (i <= mid && j <= end) {
        if (arr[i] <= arr[j]) answer[k++] = arr[i++];
        else answer[k++] = arr[j++];
    }
    
    while (i <= mid) {
    	answer[k++] = arr[i++];
    }
       
    while (j <= end) {
    	answer[k++] = arr[j++];
    }
        
    for (int i = start; i <= end; i++) {
        arr[i] = answer[i - start];
    }
}