C++에서 배열로 표현된 숫자를 재귀 호출로 1 증가시키는 방법

이번 글에서는 흥미로운 문제 하나를 살펴보겠습니다. 어떤 숫자가 주어졌을 때 이 숫자를 1만큼 증가시키는 것은 아주 간단한 작업입니다. 하지만 여기서는 숫자를 일반적인 정수 변수가 아니라 배열 형태로 다룹니다. 숫자의 각 자릿수가 배열의 요소 하나하나에 저장되며, 예를 들어 512라면 {5, 1, 2}처럼 저장됩니다.

또한 단순 반복문 대신 재귀(recursion) 방식을 사용해 숫자를 증가시켜야 한다는 조건이 있습니다. 자릿수별로 올림(carry)이 발생하는 상황도 재귀 호출로 자연스럽게 처리할 수 있습니다. 그럼 알고리즘부터 차근차근 살펴보겠습니다.

알고리즘

increment(arr, n, index) 함수의 동작 과정은 다음과 같습니다. index의 기본값은 0입니다.

begin
    if index < n, then
        if arr[index] < 9, then
            arr[index] := arr[index] + 1   // 올림 없이 바로 1 증가
        else
            arr[index] := 0                // 9였다면 0으로 만들고
            increment(arr, n, index + 1)   // 다음 자릿수를 재귀적으로 증가
    end if
    if index = n, then
        arr[n] := 1                        // 모든 자릿수가 9였던 경우 새 자릿수 추가
        n := n + 1                         // 자릿수 개수 증가
    end if
end

핵심 아이디어

현재 자릿수가 9보다 작으면 그냥 1을 더하면 끝입니다. 하지만 현재 자릿수가 9라면 1을 더했을 때 올림이 발생하므로, 해당 자릿수를 0으로 바꾸고 다음 자릿수에 대해 같은 작업을 재귀적으로 수행합니다. 만약 999처럼 모든 자릿수가 9인 숫자라면 재귀 호출이 배열의 끝(index == n)까지 도달하게 되고, 이때 새로운 자릿수 1을 추가하여 자릿수 개수를 하나 늘립니다.

구현 예제 (C++)

#include <iostream>
#include <cmath>
#define MAX 20
using namespace std;

void increment(int num_arr[], int &n, int index = 0){
    if(index < n){
        if(num_arr[index] < 9){ // 자릿수가 9보다 작으면 1을 더함
            num_arr[index]++;
        }else{ // 9라면 0으로 만들고 다음 자릿수를 재귀적으로 처리
            num_arr[index] = 0;
            increment(num_arr, n, index+1);
        }
    }
    if(index == n){
        num_arr[n] = 1; // 모든 자릿수가 9였던 경우 올림 처리
        n++; // 자릿수 개수 증가
    }
}

void dispNumber(int num_arr[], int n){
    for(int i = n-1; i>= 0; i--){
        cout << num_arr[i];
    }  
    cout << endl;
}

int numToArr(int num_arr[], int number){
    int i = 0;
    int n = log10(number) + 1; // 자릿수 개수 계산
    for(int i = i; i< n; i++){
        num_arr[i] = number % 10; // 낮은 자릿수부터 배열에 저장
        number /= 10;
    }
    return n;
}

main() {
    int number = 1782698599;
    int num_arr[MAX];
    int n = numToArr(num_arr, number);
    cout << "Initial Number: "; dispNumber(num_arr, n);
    increment(num_arr, n);
    cout << "Final Number: "; dispNumber(num_arr, n);
}

실행 결과

Initial Number: 1782698599
Final Number: 1782698600

동작 설명

위 예제에서 입력 숫자는 1782698599입니다. 이 숫자는 numToArr 함수를 통해 낮은 자릿수부터 배열에 {9, 9, 5, 8, 9, 6, 2, 8, 7, 1} 순서로 저장됩니다. increment 함수가 호출되면 가장 낮은 자릿수(일의 자리)부터 확인합니다.

일의 자리는 9이므로 0으로 바꾸고 십의 자리로 재귀 호출이 넘어갑니다. 십의 자리 역시 9이므로 같은 과정이 반복되고, 백의 자리는 5이므로 6으로 증가한 뒤 재귀가 종료됩니다. 결과적으로 1782698599는 1782698600이 됩니다.

만약 999처럼 모든 자릿수가 9인 숫자가 입력된다면, 재귀 호출이 배열의 마지막 인덱스(n)에 도달하고 그 자리에 1이 새로 추가되어 1000이 됩니다. 이처럼 재귀 구조를 활용하면 올림 처리 로직을 반복문 없이도 깔끔하게 구현할 수 있습니다.