Coding Interview

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

※ 이 포스트는 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

admin

Recent Posts

2024년 11월 17일 일요일 – 서울 생활 129주차

괌여행 아내와 함께 괌으로 여행을 갔다. 출산 이후로 둘만 가는 첫 여행이다. 하와이가 일본인들이 많이…

3일 ago

2024년 11월 3일 일요일 – 서울 생활 127주차

반복적인 일상 매일 아침 일어나 회사에 출근하고, 저녁을 먹고 돌아오는 일상의 반복이다. 주말은 가족을 보러…

3주 ago

2024년 10월 6일 일요일 – 서울 생활 123주차

Planning A well-structured plan has the following characteristics:   First, the ultimate vision you aim to…

2개월 ago

2024년 9월 29일 일요일 – 서울 생활 122주차

English The most common problem for English learners like myself is that we often use…

2개월 ago

2024년 9월 22일 일요일 – 서울 생활 121주차

추석 추석을 맞아 친가 외가 처가 어르신들을 모두 뵙고 돌아왔다. 아이가 태어난지는 좀 됐지만 한국에서…

2개월 ago

2024년 9월 8일 일요일 – 서울 생활 119주차

주말 이번주는 아내가 올라와서 주말을 함께 보냈다. 둘만 밥도 먹고 뮤지컬도 보고, 모임도 나가고 집에서…

2개월 ago

This website uses cookies.