C++로 구현하는 자릿수 배열과 정수의 덧셈: 두 수의 합 구하기

문제 소개

이 문제에서는 두 개의 수가 주어지며, 그중 하나는 일반적인 정수이고 다른 하나는 자릿수(digit) 배열로 표현되어 있습니다. 우리의 과제는 자릿수 배열 형태로 표현된 수와 일반 정수의 합을 구하는 프로그램을 작성하는 것입니다.

문제 이해를 돕는 예제

입력: n = 213, m[] = {1, 5, 8}
출력: 371
설명: 213 + 158 = 371

접근 방법

이 문제는 우리가 익히 알고 있는 세로셈 덧셈 원리를 그대로 적용하면 쉽게 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

• 배열의 마지막 요소(n-1번째)부터 시작하여 첫 번째 요소까지 역순으로 순회합니다.
• 각 단계에서 정수 n의 최하위 자릿수(LSB)를 배열의 해당 요소에 더합니다.
• 덧셈 결과가 10 이상이면 자리올림(carry)을 계산하여 다음 왼쪽 자릿수 계산에 반영합니다.

구현 예제

다음 C++ 프로그램은 위에서 설명한 해결 방법의 실제 동작을 보여줍니다.

#include <iostream>
using namespace std;

void addNumbers(int n, int size, int *m){
    int carry = 0;
    int sum = 0;
    for(int i = size-1; i >= 0; i--){
        sum = (n%10) + m[i] + carry;
        n /= 10;
        carry = sum/10;
        m[i] = sum%10;
    }
}

int main() {
    int n = 679;
    int m[] = {1, 9, 5, 7, 1, 9};
    int size = sizeof(m)/sizeof(m[0]);
    cout<<"두 수의 합(하나는 자릿수 배열로 표현됨): ";
    addNumbers(n, size, m);
    for(int i = 0; i < size; i++)
        cout<<m[i];
}

실행 결과

두 수의 합(하나는 자릿수 배열로 표현됨): 196398

참고 사항

위 구현은 결과값이 기존 배열의 크기 안에서 표현 가능하다고 가정합니다. 모든 자릿수를 더한 후에도 자리올림이 남아 있는 경우, 즉 결과가 배열 길이보다 길어질 가능성이 있다면 배열을 확장하거나 별도의 오버플로 처리 로직을 추가해야 합니다. 이 알고리즘은 배열을 한 번만 순회하므로 시간 복잡도는 배열의 길이에 비례하는 O(n)입니다.