제약 조건을 지키며 두 배열의 요소 더하기

문제 개요

이번 글에서는 두 배열의 요소를 서로 더해 새로운 배열에 저장하는 문제를 다룹니다. 단순한 덧셈처럼 보이지만, 반드시 지켜야 할 제약 조건이 있습니다. 조건은 다음과 같습니다.

덧셈은 두 배열 모두 0번째 인덱스부터 시작합니다.
합이 한 자리 수를 초과하면 각 자릿수로 분리하여 해당 위치에 순서대로 저장합니다.
길이가 더 긴 배열의 남은 요소들은 그대로 결과 배열에 저장합니다(단, 여러 자릿수라면 분리해서 저장).

그럼 이 문제를 해결하기 위한 알고리즘부터 살펴보겠습니다.

알고리즘

addArrayConstraints(arr1, arr2)

시작
    빈 벡터 out 정의
    i := 0
    i가 arr1.length와 arr2.length보다 작은 동안 반복:
        add := arr1[i] + arr2[i]
        만약 add가 한 자리 수라면:
            add를 out에 삽입
        그렇지 않으면:
            자릿수를 분리해 각각 out에 삽입
    반복 종료
    arr1에 남은 요소가 있는 동안:
        각 요소를 한 자리 수면 그대로, 아니면 분리해서 out에 삽입
    arr2에 남은 요소가 있는 동안:
        각 요소를 한 자리 수면 그대로, 아니면 분리해서 out에 삽입
끝

C++ 구현 예제

#include<iostream>
#include<vector>
using namespace std;

// 숫자를 자릿수별로 분리해 벡터에 저장하는 함수
void splitDigit(int num, vector<int> &out) {
    vector<int> arr;
    while (num) {
        arr.insert(arr.begin(), num % 10);
        num = num / 10;
    }
    out.insert(out.end(), arr.begin(), arr.end());
}

// 제약 조건에 따라 두 배열을 더하는 함수
void addArrayConstraints(int arr1[], int arr2[], int m, int n) {
    vector<int> out;
    int i = 0; // arr1과 arr2의 현재 인덱스
    while (i < m && i < n) {
        int add = arr1[i] + arr2[i];
        if (add < 10) // 한 자리 수면 합을 그대로 저장
            out.push_back(add);
        else          // 두 자리 이상이면 자릿수를 분리해 저장
            splitDigit(add, out);
        i++;
    }
    while (i < m) // arr1에 남은 요소 처리
        splitDigit(arr1[i++], out);
    while (i < n) // arr2에 남은 요소 처리
        splitDigit(arr2[i++], out);

    for (int j = 0; j < out.size(); j++)
        cout << out[j] << " ";
}

main() {
    int arr1[] = {9323, 8, 6, 55, 25, 6};
    int arr2[] = {38, 11, 4, 7, 8, 7, 6, 99};
    int n1 = sizeof(arr1) / sizeof(arr1[0]);
    int n2 = sizeof(arr2) / sizeof(arr2[0]);
    addArrayConstraints(arr1, arr2, n1, n2);
}

실행 결과

9 3 6 1 1 9 1 0 6 2 3 3 1 3 6 9 9

결과 분석

출력값이 어떻게 만들어졌는지 단계별로 확인해 보겠습니다.

9323 + 38 = 9361 → 네 자리 수이므로 9, 3, 6, 1로 분리되어 저장됩니다.
8 + 11 = 19 → 두 자리 수이므로 1, 9로 분리됩니다.
6 + 4 = 10 → 1, 0으로 분리됩니다.
55 + 7 = 62 → 6, 2로 분리됩니다.
25 + 8 = 33 → 3, 3으로 분리됩니다.
6 + 7 = 13 → 1, 3으로 분리됩니다.
이후 arr2에만 남은 요소 6은 그대로 저장되고, 마지막 99는 9, 9로 분리되어 저장됩니다.

이처럼 각 인덱스에서의 합이 한 자리 수인지 판별하고, 두 자리 이상이라면 자릿수를 하나씩 쪼개어 결과 배열에 순서대로 추가하는 방식으로 문제를 해결할 수 있습니다. 시간 복잡도는 두 배열의 길이와 각 숫자의 자릿수에 비례하며, 구현도 비교적 간단하므로 배열과 문자열 처리 연습 문제로 적합합니다.