파이썬으로 문자열 형태 숫자의 모든 부분 문자열 합계 구하기

문자열 형태로 주어진 숫자가 있을 때, 해당 숫자의 모든 부분 문자열(substring)의 합을 구하는 문제를 살펴보겠습니다. 결과값이 매우 커질 수 있으므로, 최종 답은 10⁹+7로 나눈 나머지를 반환해야 합니다.

예를 들어 입력이 s = "268"이라면, 만들 수 있는 부분 문자열은 "2", "6", "8", "26", "68", "268"이고, 이들의 총합은 다음과 같습니다.

2 + 6 + 8 + 26 + 68 + 268 = 378

문제 해결 접근 방법

모든 부분 문자열을 직접 생성하면 시간 복잡도가 급격히 증가하므로, 각 자릿수가 전체 합에 기여하는 정도를 계산하는 방식으로 접근하는 것이 효율적입니다.

핵심 아이디어는 다음과 같습니다. 특정 자릿수는 그 숫자를 포함하는 모든 부분 문자열에 등장하며, 왼쪽 방향으로 확장 가능한 시작 위치의 개수는 (i + 1)개입니다. 또한 오른쪽 방향으로 확장될 때 자리 가중치가 1, 11, 111, ... 형태로 누적되므로, 이를 변수 B로 관리하면 한 번의 역방향 순회만으로 전체 합을 구할 수 있습니다.

알고리즘 단계

• M := 10⁹ + 7 (나머지 연산에 사용할 값)
• sum_val := 0
• B := 1 (자리 가중치, 반복마다 B × 10 + 1로 갱신)
• res := 0 (결과값 저장)
• i를 문자열 길이 − 1부터 0까지 1씩 감소시키며 반복:
  • res := (res + s[i]의 숫자값 × B × (i + 1)) mod M
  • sum_val := sum_val − s[i]의 숫자값
  • B := (B × 10 + 1) mod M
• res 반환

구현 예제

다음 파이썬 코드를 통해 더 잘 이해할 수 있습니다.

def solve(s):
    M = 10 ** 9 + 7
    sum_val = 0
    B = 1
    res = 0
    for i in range(len(s) - 1, -1, -1):
        res = (res + int(s[i]) * B * (i + 1)) % M
        sum_val -= int(s[i])
        B = (B * 10 + 1) % M
    return res

s = "268"
print(solve(s))

실행 과정 추적 (s = "268")

• i = 2 (숫자 8): res = 8 × 1 × 3 = 24, B → 11
• i = 1 (숫자 6): res = 24 + 6 × 11 × 2 = 156, B → 111
• i = 0 (숫자 2): res = 156 + 2 × 111 × 1 = 378

입력

"268"

출력

378

이 알고리즘은 문자열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 매우 긴 숫자 문자열에 대해서도 효율적으로 동작합니다.