프로젝트 오일러 8번 문제

Largest product in a series

Problem 8

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?

모르는 단어

adjacent : 인접한

프로젝트 오일러 문제는 참 재밌다.  

해석 

저 네모난 1000자 짜리 수에서 인접한 4개 수의 곱 중 가장 큰 값은 9 * 9 * 8 * 9 = 5832다. 그렇다면 저 1000자리 수에서 인접한 13개 수의 곱 중 가장 큰 값은 무엇일까?

분석

인접한 13개 수의 가장 큰 곱을 만드려면 그냥 큰 수 들로만 이루어져 있으면 된다. 하지만 어떤 수들이 큰지보다 곱셈 값을 비교하는 것

훨씬 쉽고 느리지도 않을 것 같다.  13개 인접한 수에대한 점수는 곱셈 값을 사용하면 되시겠다.

그리고 위 1000자리 수를 13개씩 끊어 볼 수 있게 마스크가 있어야 한다. 물론 이 마스크는 모든 인접한 수 패턴을 보기 위해 한 칸씩 이

동한다.

방법

각각의 13개 수들을 리스트로 만든 후 함수에 넣어 점수를 비교하고 점수가 가장 큰 리스트의 곱을 출력하는 프로그램을 짜면 문제가 풀

릴 것이다. 

코드

from functools import reduce
#from time import time
def mask(series, p_len):
    maxim = 0
    ans = []
    mult = lambda x, y: x*y
    
    for i, e in enumerate(series):
        li = [int (i) for i in series[i:p_len+i]]
        score = reduce(mult, li)
        maxim, ans = (score, li) if score>maxim else (maxim, ans)
               
    return reduce(mult, ans)
    
    



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

#start_t = time()

series = series.replace(series[50],'')

print(mask(series, 13))

#print(time()-start_t)

#23514624000
#0.031212806701660156 secs

 ㅎ 사실 맘에 드는 코드가 너무 한번에 나와버렸다. 실력이 늘고 있다는 증거 일지도 모르겠다.

1000자리 수는 너무 커서 int형에 담을 수 없기에 문자열로 처리하고, 개행 문자를 지워줬다. 그냥 오른쪽으로 이어서 쓸 수도 있었겠지만 미

관상 블로그에 올리기 어려울 것 같아 이렇게 처리했다. series[50]은 '\n'로 대체할 수 있다.

사실 처음에는 문제 분석에서 계획한 마스크는 series, pattern 길이, index를 받아서 index에따라 13개짜리 리스트를 반환하는 형식이었지만

for문 안에서 큰 인자를 넣어주며 계속 호출하는 방식은 낭비가 심한 느낌이라 mask함수에서 모든 과정을 하게 다시 설계했다.

시리즈에서 13개 수를 가져와서 리스트에 하나하나 넣어준 다음,

람다 식과 reduce를 이용해 리스트 아이템들의 곱을 구하고 max값이 갱신 될 때 ans 리스트를 같이 갱신하여 maxim점수를 가진 리스트가 

ans에 저장되게 하였다.

mask(series, 4)를 넣으면 문제에서 제시해준 5832가 잘 나온다. 굳.

문제는 풀었지만 한 가지 마음에 걸리는 일이라면 i 값이 1000에 다다르는 지점에서 13개짜리 리스트가 아닌 8개, 5개 짜리 리스트가 나올수

도 있다는 것이다. 물론 이런 리스트는 정답과 거리가 멀기에 상관없지만 인접한 수들의 가장 작은 곱(0이 없을 때)을 구하는 문제였다면 오답

을 도출했을 것이다. 

리스트 길이를 확인하는 최종 완성본

from functools import reduce
#from time import time
def mask(series, p_len):
    maxim = 0
    ans = []
    mult = lambda x, y: x*y
    
    for i, e in enumerate(series):
        li = [int (i) for i in series[i:p_len+i]]
        if(len(li)!=p_len):
            break
        score = reduce(mult, li)
        maxim, ans = (score, li) if score>maxim else (maxim, ans)
               
    return reduce(mult, ans)
    
    



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

#start_t = time()

series = series.replace('\n','')

print(mask(series, 13))

#print(time()-start_t)

#23514624000
#0.031212806701660156 secs

그리고 게시판에서 dict를 사용하는 코드를 찾았다.

def problem_8(data):
    data_list = []
    for i in range(len(data)-12):
        key = data[i:i+13]
        has_a_zero = True
        for char in key:
            if char == '0':
                has_a_zero = False
                break
        if has_a_zero == True:
            data_list.append(key)

    data_d = {}
    for keys in data_list:
        value = 1
        for i in keys:
            value *= int(i)
        data_d[keys] = value

    return max(data_d.values())

내 코드보다 직관적이고 깔끔한 느낌이 좋아 가져왔다.  

나도 len(data)-12 하는 방법이 확실히 더 옳다고 생각한다.