Problem_008_Largest product in a series

[그림 01] Problem 008 문제

문제 이름 : 가장 큰 곱(product)

문제 내용 : 네 개의 가장 인접한 숫자들로 이루어진 천의 자리 가장 큰 곱은 9 * 9 * 8 * 9 = 5832입니다. 즉, 위의 숫자 나열 중에 9989라고 연속되어 있는 숫자가 있고, 이 숫자들의 곱이 4개의 숫자 중 가장 큰 것이라는 의미입니다. 그렇다면, 열 세 개의 숫자가 나열되어 있는 것들 중 가장 큰 곱을 가지고 있는 것은 무엇입니까?

위의 문제는 4개의 연속된 숫자 중 가장 큰 곱이 나올 숫자를 찾아보니 9989라는 숫자로 9 * 9 * 8 * 9가 되어 5832라고 하였습니다.

그렇다면 우리는 13개의 연속된 숫자 중 가장 큰 곱이 나올 숫자를 찾아 그 값을 출력해야 합니다.

우리는 다음과 같은 조건이 부여된 것입니다.

1. 13자리 자리씩 끊어서 가장 큰 곱이 나오는 것을 찾도록 해야 함

1. 13자리를 각각 곱해야 함

#Problem 008
#Python 3 version source
 
import operator
 
Number = """7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450"""
 
NumberList  = list(Number) #Number List
ProductDict = {}           #New dictionary type
position    = 0
num         = 1
 
while(position+13 < len(NumberList)):
  for i in range(position, position+13):
    num *= int(NumberList[i])
  ProductDict[num] = Number[position:position+13]
  num = 1
  position += 1
   
sorted_ProductDict = sorted(ProductDict.items(), key=operator.itemgetter(1)) #key 값으로 정렬
#sorted_ProductDict = sorted(ProductDict.items(), key=operator.itemgetter(0)) #value 값으로 정렬
print(sorted_ProductDict)

이제 소스코드를 작성해보도록 하겠습니다.

위와 같이 Number에 숫자를 모두 넣어주고 13칸 씩 이동하면서 각 숫자를 모두 더하여, 가장 큰 숫자를 프린트하도록 합니다.

ProductList는 13개의 숫자를 곱하여 나온 값을 하나하나 List로 저장하는 것이고, 이를 sort()함수로 정렬한 뒤, 가장 큰 숫자를 출력하도록 했습니다.

메모리적 이득을 보기 위해서는 set()을 쓰는 것도 괜찮은 방법이라고 생각합니다.

또한 소스에서 21번째 라인을 보시게 되면 key 값으로 정렬하지 않고 value 값으로도 정렬할 수 있습니다.

이제 저보다 겁나 잘하는 사람의 소스를 가져와서 비교해보도록 할 것입니다.

마음의 준비를 해야겠네요..

s = '7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450'
n = 0
for i in range(0, len(s)-4):
    p = 1
    for j in range(i,i+5):
        p = p * int(s[j])
    if p > n: n = p
 
print(n)

이 소스는 13개의 숫자가 아니라 5개의 숫자를 곱한 값을 구하는 공식입니다.

확실히 더 효율적으로 보입니다.

굳이 List에 저장할 필요 없이 더 크면 저장하고 크지 않으면 저장하지 않는 알고리즘이 더 메모리를 아낄 수 있는 것 같습니다.