Sam and substrings

사이트: HackerRank
난이도: 미디움
분류: Dynamic programming

문제

정수형 문자열이 주어질 때, 각 하위 문자열들의 합을 구해서 반환하라

n = 1234
1 + 2 + 3 + 4 + 12 + 23 +34 + 123 + 234 + 1234 = 1670
return 1670

1. 나의 풀이

dp 문제는 유형을 다양하게 접하기 위해 고민 시간을 짧게 가지려 한다. 대략적으로 생각했을 때 머리속에 떠오른 아이디어는 아래와 같았다.

1 + 12 + 123 + 1234
2 + 23 + 234
3 + 34
4

위와 같은 하위 문자열을 얻기 위해 반복문을 2번 돌리면 되지 않을까? 그러나 해당 접근 방식으로는 시간 복잡도 제한을 해결할 수가 없어서 풀이법을 찾아보았다.

2. 다른사람의 풀이

해당 문제는 문제의 이해보다 해결방법이 더 이해하기 어려웠던 것 같다. 몇가지 내용들을 찾아보다가 geeksforgeeks에서 자세하게 설명해준 내용을 참고하였다.

접근 방식

내가 접근했던 방식과 반대로 해당 풀이법은 뒤를 기준으로 조합한다.

sumOfDigit[0] = 1
sumOfDigit[1] = 2 + 12
sumOfDigit[2] = 3 + 23 + 123
sumOfDigit[3] = 4 + 34 + 234 + 1234

return total(sumOfDigit)

위 내용을 토대로 하면 아래 수식을 뽑아낼 수 있다.

sumOfDigit[i] = ((i + 1) * (numberStr[i])) + (10 * sumOfDigit[i - 1])

처음에는 왜 저렇게 수식이 나오는지 이해가 가지 않았는데, sumOfDigit[i]를 계산하는 라인 하나만 뽑아서 풀이해보면 위 수식에 대해 이해할 수 있게 된다.

sumOfDigit[3] = 4 + 34 + 234 + 1234

위 수식은 아래와 같이 풀 수 있다.

4 + (30 + 4) + (230 + 4) + (1230 + 4)

4가 마지막에 오는 수들을 풀어보면 총 네 번 4가 반복된다는 것을 알 수 있다. 따라서 해당 규칙은 아래와 같이 정의된다.

// (3 + 1) * (4)
(i + 1) * (numberStr[i])

마지막으로 풀어서 쓰여진 수식을 잘 살펴보면, 4를 제외한 숫자들을 모아서 봤을 때 이전(i=2)에 계산된 숫자들의 패턴이 보이는 것을 확인 할 수 있다.

4 + (30 + 4) + (230 + 4) + (1230 + 4)
// 위 수식에서 4를 제외한 숫자들만 뽑아보면 아래와 같다.
30 + 230 + 1230

4를 제외한 숫자들의 패턴이 이전(i=2) 값에서 10을 곱한 숫자와 같다는 것을 알 수 있다.

// 이전 값(i=2)
sumOfDigit[2] = 3 + 23 + 123

따라서 해당 규칙을 수식으로 변환하면 아래와 같아진다.

// sumOfDigit[2] = 149
10 * sumOfDigit[i - 1]

위 내용을 따라가다 보면 수식을 이해하기 어렵지 않을 것이다.
아래 전체 로직을 보고 흐름을 파악해 보자.

function substrings(n) {
    // Write your code here
    const MOD = Math.pow(10, 9) + 7;

    let sumOfDigit = new Array(n.length);
    sumOfDigit[0] = +n[0];
    let res = sumOfDigit[0];

    for (let i = 1; i < n.length; i++) {
        sumOfDigit[i] = ((i + 1) * (+n[i])) + (10 * sumOfDigit[i - 1]);
        sumOfDigit[i] = sumOfDigit[i] % MOD;
        res = (res + sumOfDigit[i]) % MOD;
    }

    return res;
}