Xzero

Xzero

Mathematics, Coding

Q8_Largest product in a series

들어가기

오늘 살펴볼 문제는 Q8 입니다.
https://projecteuler.net/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?

주어진 1000개의 연속된 숫자에서 13개의 연속된 곱의 최댓값을 구하라는 문제입니다.
편의상 숫자는 50개씩 하나의 열로 썼지만 1000개의 연속된 숫자로 보아야하는 것 같네요.

필요한 문법들

우선 위의 문제는 다음과 같은 순서로 진행하도록 하겠습니다.

  1. 주어진 50*20개의 숫자를 1000개의 숫자로 인식하도록 처리
  2. 13개의 곱을 처음부터 계산해서 최댓값을 구하기

우선 1을 설명하기 위해서 다음 코드를 봅시다.

mytest= """ 123
            456
789"""
print("print",mytest)
print("repr",repr(mytest))

위의 코드를 실행시키면 다음과 같은 문자열이 반환됩니다.

print  123
            456
789
repr ' 123\n            456\n789'
  • 여기서 """ 는 여러줄 문자열을 만드는 문법입니다. 위처럼 여러행이 있는 문자열을 넣을 때 사용합니다.
  • repr으로 리턴한 문자열은 ‘파이썬으로 해당 객체를 만들 수 있게 해주는 공식적인 문자열’ 입니다. 음 쉽게 말해 출력하고자 하는 객체의 본 모습을 출력한다고나 할까요?
  • print(mytest)는 출력하는 문자열을 사람이 읽기 쉽도록 일정한 규칙을 적용하여 출력하게 됩니다.
  • 위의 결과를 참고하면 print(repr(mytest))을 통해 mytest를 보기좋게 출력하기 위해 숨어있는 문자열을 확인할 수 있습니다. 빈칸과 \n이 들어있네요.
  • \n은 다음행으로 출력하는 것을 나타냅니다.

그렇다면 위의 mytest의 문자열을 우리의 문제에서와 같이 9개의 숫자가 연속하도록 만들기 위해서는 아래와 같이 실행하며 됩니다.

print(mytest.replace("\n", "").replace(" ",""))
  • 첫번째 replace를 통해 문자열에 숨어있는 \n을 제거합니다.
  • 두번째 replace를 통해 문자열에 숨어있는 빈칸을 모두 제거합니다.
    위를 실행하면 아래와 같은 결과를 얻습니다.
123456789

예시코드

이제 위의 결과를 적용하여 예시코드를 만들어 보면 아래와 같습니다.

text = """73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450 """
clean_data = text.replace("\n", "").replace(" ","")

def list_product(mylist):
    myr = 1
    for i in mylist:
        myr = myr * int(i)
    return myr

result = 0
component = 0
for i in range(0, 1000):
    if result < list_product(clean_data[i:i + 13]):
        result = list_product(clean_data[i:i + 13])
        component = clean_data[i:i + 13]

print("가장 큰 값은 {}이고 이때 숫자의 조합은 {}이다. ".format(result, component))

# 가장 큰 값은 23514624000이고 이때 숫자의 조합은 5576689664895이다.
  • clean_data는 1000개의 문자열 안에 빈칸과 개행문자(\n)을 소거하여 만든 연속된 1000자리 숫자이다.
  • list _product는 리스트를 받아서 리스트의 원소의 곱을 반환한다.
  • result는 곱의 최댓값을 넣기 위해 만든 변수이다.
  • component는 1000개의 숫자중에서 반복문안에서 곱을 계산하는 13개의 숫자를 담는 변수이다.
  • for문을 통해 13개의 숫자의 곱을 비교하고 가장 큰값에 해당하는 값을 result와 component에 담고 마지막에 출력한다.

마무리

이 문제는 수학보다는 데이터를 처리하는 파이썬의 기능이 필요한 문제네요.
이런 식의 전처리에 파이썬이 많이 활용되고 있습니다.

덧붙임

위의 코드와 관련하여

print(clean_data[2010:2012])
print(clean_data[1010])

clean_data는 1000개의 숫자로 이루어진 문자열이므로 위의 코드 둘다 IndexError를 나타낼 것 같지만,
각각 하나씩 실행시켜보면 위의 것은 오류없이 빈칸을 출력하고 아래 것은 IndexError를 만들어냅니다.
이유도 한번 찾아보면 좋을 것 같습니다~ . 알아두면 좋을 만한 Tip이었습니다.

Leave a Comment