C++로 판별하는 합 문자열(Sum String): 주어진 문자열이 합 문자열인지 확인하는 방법

합 문자열(Sum String)이란 무엇일까요?

이 글에서는 C++을 이용해 주어진 문자열이 합 문자열(sum-string)인지 판별하는 방법을 살펴보겠습니다. 합 문자열이란, 문자열의 맨 오른쪽 부분 문자열이 바로 앞에 있는 두 부분 문자열의 합으로 표현될 수 있고, 이 규칙이 앞쪽 부분 문자열들에 대해서도 재귀적으로 계속 성립하는 문자열을 의미합니다.

예를 들어 문자열 12243660을 보겠습니다.

12 + 24 = 36 → 문자열 안에서 12와 24 바로 뒤에 36이 등장합니다.
24 + 36 = 60 → 이어서 36 뒤에 60이 등장합니다.

이처럼 연속된 세 부분 문자열마다 "첫 번째 수 + 두 번째 수 = 세 번째 수"라는 관계가 유지되므로, 해당 문자열은 합 문자열입니다.

수학적 정의

문자열 S가 아래 조건들을 만족하면 합 문자열이라고 할 수 있습니다.

substring(i, x) + substring(x+1, j) = substring(j+1, l)

substring(x+1, j) + substring(j+1, l) = substring(l+1, m)

핵심은 이러한 관계가 문자열의 끝에 도달할 때까지 반복해서 성립해야 한다는 점입니다.

풀이 접근 방법

이 문제는 크게 두 단계로 나누어 해결할 수 있습니다.

문자열 덧셈 함수: 숫자가 매우 커서 정수형 변수의 범위를 넘을 수 있으므로, 두 숫자 문자열을 직접 더하는 함수를 구현합니다. 각 자릿수를 뒤에서부터 더하면서 올림수(carry)를 처리합니다.
재귀적 검증: 첫 번째와 두 번째 부분 문자열의 길이를 다양하게 조합해 가며, 두 수의 합이 문자열의 다음 부분과 일치하는지 재귀적으로 확인합니다. 문자열 끝까지 이 관계가 유지되면 해당 문자열은 합 문자열입니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;

// 두 숫자 문자열을 더해 결과를 문자열로 반환하는 함수
string get_string_sum(string str1, string str2) {
    if (str1.size() < str2.size())
        swap(str1, str2);
    int len1 = str1.size();
    int len2 = str2.size();
    string ans = "";
    int carry = 0;
    // 공통 자릿수끼리 더하기
    for (int i = 0; i < len2; i++) {
        int ds = ((str1[len1 - 1 - i] - '0') + (str2[len2 - 1 - i] - '0') + carry) % 10;
        carry = ((str1[len1 - 1 - i] - '0') + (str2[len2 - 1 - i] - '0') + carry) / 10;
        ans = char(ds + '0') + ans;
    }
    // 남은 자릿수 처리
    for (int i = len2; i < len1; i++) {
        int ds = (str1[len1 - 1 - i] - '0' + carry) % 10;
        carry = (str1[len1 - 1 - i] - '0' + carry) / 10;
        ans = char(ds + '0') + ans;
    }
    // 마지막 올림수 처리
    if (carry)
        ans = char(carry + '0') + ans;
    return ans;
}

// 재귀적으로 합 문자열 여부를 검증하는 헬퍼 함수
bool sumStrCheckHelper(string str, int beg, int len1, int len2) {
    string sub1 = str.substr(beg, len1);
    string sub2 = str.substr(beg + len1, len2);
    string sum = get_string_sum(sub1, sub2);
    int sum_len = sum.size();
    // 합을 담을 공간이 부족하면 실패
    if (sum_len > str.size() - len1 - len2 - beg)
        return false;
    if (sum == str.substr(beg + len1 + len2, sum_len)) {
        // 문자열 끝에 도달했다면 성공
        if (beg + len1 + len2 + sum_len == str.size())
            return true;
        // 시작 위치를 이동시켜 재귀 검증
        return sumStrCheckHelper(str, beg + len1, len2, sum_len);
    }
    return false;
}

bool isSumStr(string str) {
    int n = str.size();
    // 첫 두 부분 문자열의 모든 길이 조합 시도
    for (int i = 1; i < n; i++)
        for (int j = 1; i + j < n; j++)
            if (sumStrCheckHelper(str, 0, i, j))
                return true;
    return false;
}

int main() {
    if(isSumStr("1212243660"))
        cout << "This is sum-string";
    else
        cout << "This is not sum-string";
}

코드 설명

get_string_sum(): 두 숫자 문자열을 받아 합을 문자열 형태로 반환합니다. 짧은 쪽 문자열 길이만큼 자릿수를 더하고, 남은 자릿수와 최종 올림수까지 처리하여 오버플로우 없이 큰 수의 덧셈을 지원합니다.
sumStrCheckHelper(): 시작 위치 beg에서 길이가 각각 len1, len2인 두 부분 문자열을 추출한 뒤, 그 합이 뒤따르는 부분 문자열과 일치하는지 검사합니다. 일치하면 시작 위치를 앞으로 이동시켜 재귀 호출하고, 문자열 끝에 정확히 도달하면 true를 반환합니다.
isSumStr(): 가능한 모든 첫 번째/두 번째 부분 문자열 길이 조합(i, j)을 시도하여, 하나라도 성공하면 true를 반환합니다.

실행 결과

This is sum-string

입력 문자열 "1212243660"은 12 + 12 = 24, 12 + 24 = 36, 24 + 36 = 60의 관계를 차례로 만족하므로 합 문자열로 판정됩니다.

시간 복잡도 및 공간 복잡도

첫 두 부분 문자열의 길이 조합을 선택하는 데 O(n²)이 소요되고, 각 조합에 대한 검증 과정에서 문자열 덧셈과 비교가 반복되므로 전체 시간 복잡도는 최악의 경우 O(n³)입니다. 공간 복잡도는 재귀 호출 스택과 임시 문자열 저장을 위해 O(n)입니다.