[알고리즘] 10. Sam and Substrings

Samantha and Sam are playing a numbers game. Given a number as a string, no leading zeros, determine the sum of all integer values of substrings of the string. For example, if the string is , the substrings are  and . Their sum is .

Given an integer as a string, sum all of its substrings cast as integers. As the number may become large, return the value modulo .

Function Description

Complete the substrings function in the editor below. It should return the sum of the integer values of all substrings in a string representation of a number, modulo .

substrings has the following parameter(s):

• n: the string representation of an integer

Input Format

A single line containing an integer as a string without leading zeros.

Constraints

Output Format

A single line which is sum of the substrings, 

Sample Input 0

16

Sample Output 0

23

Explanation 0

The substring of number 16 are 16, 1 and 6 which sums to 23.

Sample Input 1

123

Sample Output 1

164

Explanation 1

The sub-strings of 123 are 1, 2, 3, 12, 23, 123 which sums to 164.

답 : 

#!/bin/python3

import math

import os

import random

import re

import sys

# Complete the substrings function below.

def substrings(n):

numSum = 0

for i in range(len(n)):

numSum += (int(n[i])*(int('1'*(len(n)-i)))*(i+1))

if 1 <= int(n) <= 2*(10**5):

numSum = numSum

else:

numSum = numSum % (10**9+7)

return numSum

if __name__ == '__main__':

fptr = open(os.environ['OUTPUT_PATH'], 'w')

n = input()

result = substrings(n)

fptr.write(str(result) + '\n')

fptr.close()

숫자들에 대해서 기본적으로 다음과 같이 계산이 된다.

예를 들어서 4231이라는 숫자가 있으면 

하나씩 쪼개 보면 다음과 같다

4 / 42 / 423 / 4231

2 / 23 / 231

3 / 31

1 /

이를 한 줄 씩 뜯어보면 다음과 같은 공식을 얻어낼 수 있다. 

K * 1의 갯수() * n

여기서 K는 각 자릿수에 해당하는 숫자이다. 만약 k=1일경우 4를 말하고 k=2라면 2를 말하는 것이다.

1의 갯수는 내림차순으로 전체 숫자 배열의 길이부터 시작한다. 여기서는 4자리이기에 4개의 1인 1,111이 곱해지는 것이다. 

그리고 마지막 n의 경우는 반대로 1부터 2,3,4,,,, 순서대로 곱해지면 된다. 파이썬은 0부터 이기에 i+1로 표기했다.

 

이렇게 실행해본 결과... 6개의 경우는 시간 초과로 성공하지 못하였다. 

코드를 조금 더 깔끔하고 불필요한 것을 제거해봐야겠다!