[코딩 인터뷰][HackerRank] Sam and Substring

Posted on by

※ 이 포스트는 HackerRank 문제인 Sam and Substring 해설을 담고 있습니다.
본 풀이는 Optimal하지 않을 수 있으며, HackerRank에서의 Submission 통과만을 보장합니다.

문제 정보

문제 출처 : Sam and Substring (https://www.hackerrank.com/challenges/sam-and-substrings/problem)
카테고리 : DP
난이도 : 쉬움

문제 설명

어떤 수 N이 주어진다. N은 2 x 10^5 자리 이하의 자연수다.
이 수를 String으로 간주해서 가능한 모든 SubString을 추출하여 합한 값을 출력하여라.
예를 들어 123의 경우, [1, 2, 3, 12, 23, 123]의 합을 출력하면 된다.

문제 설명을 좀 더 추가하자면 이 SubString은 중복을 포함한다.
예를 들어 111과 같은 수라면 [1, 1, 1, 11, 11, 111]의 합을 출력하면 된다.

SubString 중에서 맨 앞이 0인 것도 수로 인정된다.
1010의 경우 [1, 0, 1, 0, 10, 01, 10, 101, 010, 1010]의 합을 출력하면 된다.
여기서 01은 1로, 010은 10으로 간주된다.

문제 풀이

문제 가장 간단히 풀려면 인덱스 i와 j에 대해 N[ i : j ]의 SubString을 모두 구해서 합하면 된다.
이 방식은 O(N^2)의 수행시간으로, 시간초과인 TLE를 받는다.

어떤 인덱스 j에 대해 N[i]를 끝으로 한 모든 수들을 생각해보자.
그 수들은 N[i] 한 자리만 있는 경우를 제외하면, N[i – 1]을 끝으로 한 모든 수의 뒤에 N[i]를 붙인 것과 같다.

가장 처음인 i = 0인 경우엔 N[i] 하나밖에 없다.
i = 1인 경우엔, N[i-1]N[i]이나 N[i] 둘이 존재한다.
즉, 가능한 수들의 갯수는 i + 1개와 동일하다.

이걸 종합해서 tmp = tmp * 10 + (i + 1) * int(N[i])이고 매번 tmp를 누적해서 리턴하면 된다.
단, 결과가 10^9 + 7를 넘는 경우 나머지만 출력하므로 매 연산마다 나머지 연산을 해주는게 좋다.

코드
#!/bin/python3

import math
import os
import random
import re
import sys

# Complete the substrings function below.
def substrings(n):
    ret, tmp = 0, 0
    for i in range(len(n)):
        tmp = (tmp * 10 + int(n[i]) * (i + 1)) % (10 ** 9 + 7)
        ret = (ret + tmp) % (10 ** 9 + 7)
    return ret


if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    n = input()

    result = substrings(n)

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

    fptr.close()

코딩 인터뷰 – Sam and Substring