숫자가 포함된 문자열이 주어졌을 때, 재귀(recursion) 기반의 atoi() 구현을 통해 이에 대응하는 정수 값을 구하는 것이 목표입니다. C 표준 라이브러리의 int atoi(const char *str) 함수는 문자열 인수 str을 정수(int) 타입으로 변환하는 역할을 합니다.
예제
입력 − Str[] = "58325"
출력 − 변환된 정수 값 : 58325
설명 − 문자열 "58325"에 해당하는 숫자는 58325입니다.
입력 − Str[] = "00010"
출력 − 변환된 정수 값 : 10
설명 − 앞의 0은 무시되며, 문자열에 해당하는 숫자는 10입니다.
알고리즘 접근 방식
이 접근법에서는 입력 문자열과 그 길이를 받아 각 문자를 하나씩 처리하는 재귀 함수 recurAtoi()를 사용합니다. 각 자릿수를 십진수로 변환한 뒤 10을 곱하고, 이전 단계의 결과를 더하는 방식으로 전체 숫자를 만들어냅니다.
- 숫자가 담긴 입력 문자열 Str[]을 받습니다.
strlen(Str)을 사용하여 문자열의 길이를 계산합니다.- 함수
recurAtoi(char *str, int len)는 입력을 받아 재귀적으로 계산된 정수를 반환합니다. - 길이가 1이라면 마지막 한 자리이므로
*str - '0'을 반환합니다. temp = 10 * recurAtoi(str, len - 1)로 이전까지의 결과에 10을 곱해 자릿수를 밀어냅니다.temp = temp + str[len - 1] - '0'으로 현재 자릿값을 더합니다.- 최종적으로 temp를 반환하고 결과를 출력합니다.
구현 예제 코드
#include <bits/stdc++.h>
using namespace std;
int recurAtoi(char *str, int len){
if (len == 1){
return *str - '0';
}
int temp = 10 * recurAtoi(str, len - 1);
temp = temp + str[len - 1] - '0';
return (temp);
}
int main(void){
char Str[] = "58325";
int length = strlen(Str);
cout << "Equivalent decimal : " << recurAtoi(Str, length);
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
Equivalent decimal : 58325
동작 원리 요약
재귀 호출은 문자열의 가장 왼쪽 자릿수부터 시작해 길이를 줄여가며 진행됩니다. 가장 깊은 호출(마지막 한 자리)부터 결과가 거슬러 올라오면서 매번 10을 곱해 자릿수를 확장하고 새 자릿값을 더하는 방식으로, 최종적으로 전체 문자열이 하나의 정수로 변환됩니다. 이 과정의 시간 복잡도는 O(n), 공간 복잡도 역시 재귀 호출 스택으로 인해 O(n)입니다.