C++에서 두 배열의 요소를 교차 병합해 세 번째 배열 만들기

문제 개요

두 개의 배열이 주어졌을 때, 첫 번째 배열과 두 번째 배열의 요소를 번갈아 가며 배치한 새로운 배열(세 번째 배열)을 만들어야 합니다. 이때 한쪽 배열에 요소가 더 많이 남아 있다면, 남은 요소들은 결과 배열의 맨 뒤에 순서대로 추가하면 됩니다.

arr1[] = {10, 20, 30, 40}
arr2[] = {-10, -20, -30, -40}
result[] = {10, -10, 20, -20, 30, -30, 40, -40}

위 예시에서 볼 수 있듯이, 첫 번째 배열의 요소와 두 번째 배열의 요소가 한 개씩 교대로 배치되어 최종 결과 배열이 완성됩니다.

알고리즘

1. 두 배열을 동시에 순회하면서 각 배열의 요소를 하나씩 번갈아 결과 배열에 저장합니다.
2. 한쪽 배열의 모든 요소를 먼저 처리했다면, 다른 배열에 남은 요소들을 결과 배열의 끝에 추가합니다.

동작 방식

두 인덱스 i와 j를 각각 첫 번째 배열과 두 번째 배열의 위치를 가리키도록 초기화한 뒤, 두 배열 중 어느 하나라도 끝에 도달할 때까지 반복문을 수행합니다. 반복이 종료된 후에는 아직 처리하지 못한 배열의 나머지 요소들을 순서대로 결과 배열에 덧붙입니다. 이 알고리즘의 시간 복잡도는 두 배열의 길이의 합에 비례하는 O(n1 + n2)입니다.

예제 코드

#include <iostream>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;
void alternateMergedArray(int *arr1, int n1, int *arr2, int n2,int *result){
    int i, j, k;
    i = 0;
    j = 0;
    k = 0;
    while (i < n1 && j < n2) {
        result[k] = arr1[i];
        ++k;
        ++i;
        result[k] = arr2[j];
        ++k;
        ++j;
    }
    while (i < n1) {
        result[k] = arr1[i];
        ++k;
        ++i;
    }
    while (j < n2) {
        result[k] = arr2[j];
        ++k;
        ++j;
    }
}
void displayArray(int *arr, int n){
    for (int i = 0; i < n; ++i) {
        cout << arr[i] << " ";
    }
    cout << endl;
}
int main(){
    int arr1[] = {10, 20, 30, 40};
    int arr2[] = {-10, -20, -30, -40};
    int result[SIZE(arr1) + SIZE(arr2)];
    cout << "First array: " << endl;
    displayArray(arr1, SIZE(arr1));
    cout << "Second array: " << endl;
    displayArray(arr2, SIZE(arr2));
    cout << "Result array: " << endl;
    alternateMergedArray(arr1, SIZE(arr1), arr2, SIZE(arr2),result);
    displayArray(result, SIZE(result));
    return 0;
}

출력 결과

위 프로그램을 컴파일하고 실행하면 다음과 같은 결과가 출력됩니다.

First array:
10 20 30 40
Second array:
-10 -20 -30 -40
Result array:
10 -10 20 -20 30 -30 40 -40