8. Largest product in a series

projecteuler.net/problem=8

Problem 8 - Project Euler

 

문제는 다음과 같습니다.

The four adjacent digits in the 1000-digit number that have the greatest product are 9 × 9 × 8 × 9 = 5832.

73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450

 

Find the thirteen adjacent digits in the 1000-digit number that have the greatest product. What is the value of this product?

 

주어진 1000 개의 숫자 열에서 4개의 인접한 숫자들의 곱 중 가장 큰 경우의 수는 9 * 9 * 8 * 9 = 5832이다.

13개의 인접한 숫자들의 곱 중 가장 큰 경우의 수는 얼마인가? 를 구하는 문제입니다.

 

처음 문제를 보았을 때에 인접한 숫자라는 것이 어떤 것을 의미하는지가 정확히 나와있지 않으므로, 헷갈릴 수 있습니다.(저만 그런지는 잘 모르겠네요 ;;)

하지만 해당 문제는 어렵게 생각할 필요가 없이, 하나의 숫자를 시작으로 가로로 몇개의 숫자가 나열되어 있는가로 생각하면 되는 문제였습니다.

 

ex) 31998900047482166370484403199890008895

 

이 문제를 푸는 방식 또한 마찬가지로 brute force를 이용하였습니다. 다른 방법은 떠오르지 않았기 때문입니다. 대신, 해당 문제에서는 파이썬에서 문자열을 어떤식으로 다루는가 에 대하여 공부하는 방향이었던 것으로 기억합니다.

 

구성한 코드의 알고리즘은 간단합니다.

1. 0번째 숫자부터 시작한다.

2. 지정된 숫자로부터 오른쪽으로 n번째 까지의 곱을 구한다.

3. 여태까지 구한 숫자의 곱보다 크면 해당 숫자를 가장 큰 수로 저장한다

 

입니다.

 

코드는 아래와 같습니다.

 

# input : String number
# output : number that 0's index
# input Striing number and return number that 0's index
## if zero is not in String, return -1
def findZeroInStr(nStr) :
    for i in range(0, len(nStr)) :
        if nStr[i] == "0" :
            return i

    return -1

# input : String number
# output : product what element of String number's
# input Stirng number, return product what element of String number's
def strElementProduct(nStr) :
    res = 1
    for i in nStr :
        res *= int(i)

    return res

strLen = len(nStr)
maxProduct = 0
for i in range(0, strLen - 13) :
    tmp = ""
    for j in range(i, i + 13) :
        tmp += nStr[j]
        s = findZeroInStr(tmp)
    if s != -1 :
        i += s
        continue
    p = strElementProduct(tmp)
    if maxProduct < p :
        print("i : ",i)
        maxProduct = p

print(maxProduct)