오일러 프로젝트 8 번 문제는 1000개의 연속된 숫자에서, 연속한 5개의 부분열의 곱을 계산하여 그 중 가장 큰 값을 찾는 문제이다.
다음은 연속된 1000자리 숫자입니다 (읽기 좋게 50자리씩 잘라놓음)
73167176531330624919225119674426574742355349194934 96983520312774506326239578318016984801869478851843 85861560789112949495459501737958331952853208805511 12540698747158523863050715693290963295227443043557 66896648950445244523161731856403098<span style="color: #ff0000;">71112</span>1722383113 62229893423380308135336276614282806444486645238749 30358907296290491560440772390713810515859307960866 70172427121883998797908792274921901699720888093776 65727333001053367881220235421809751254540594752243 52584907711670556013604839586446706324415722155397 53697817977846174064955149290862569321978468622482 83972241375657056057490261407972968652414535100474 82166370484403199890008895243450658541227588666881 16427171479924442928230863465674813919123162824586 17866458359124566529476545682848912883142607690042 24219022671055626321111109370544217506941658960408 07198403850962455444362981230987879927244284909188 84580156166097919133875499200524063689912560717606 05886116467109405077541002256983155200055935729725 71636269561882670428252483600823257530420752963450여기서 붉게 표시된 71112의 경우 7, 1, 1, 1, 2 각 숫자를 모두 곱하면 14가 됩니다. 이런 식으로 맨 처음 (7 × 3 × 1 × 6 × 7 = 882) 부터 맨 끝 (6 × 3 × 4 × 5 × 0 = 0) 까지 5자리 숫자들의 곱을 구할 수 있습니다. 이렇게 구할 수 있는 5자리 숫자의 곱 중에서 가장 큰 값은 얼마입니까?
출처 : 한글판 오일러 프로젝트 8번(http://euler.synap.co.kr/prob_detail.php?id=8)
접근
결국 1000개의 숫자가 일렬로 늘어서 있고, 이 중에서 연속하는 다섯개의 숫자의 곱 중에서 가장 큰 값을 구하는 것이다.
- 가장 앞의 숫자 5개는 0번~4번 인덱스 범위를 갖는다.
- 1번에서 5번, 2번에서 6번… 이렇게 5개 숫자에 대해서 반복하면서
- 각 숫자를 정수로 변환하고 곱하는 값으로 변환한 후
- 그 중에서 가장 큰 값을 구하면 된다.
여기서 요구되는 스킬은 다음과 같다.
- 여러 줄로 나눠서 쓴 문자열을 하나의 숫자 시퀀스로 변환하기
- 숫자시퀀스를 정수의 리스트로 변환하기
- 5마디씩의 곱으로 변환하기
5마디의 곱을 구하는 것은 reduce 함수가 필요하다. 예를 들어 정수 리스트의 첫 5개의 곱을 구한다고 하면 , reudce(lambda x, y: x*y, aList[0:5], 1)라는 코드를 사용할 수 있을 것이다. 여기서 범위인 0~5를 i:i+5라 하고, 0~9995 사이의 i에 대해서 5마디의 곱을 구한 후 최대값을 찾으면 된다.
from functools import reduce
s = """73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450"""
# 먼저 주어진 문자열을 한 줄로 합친 후, 각 글자를 정수로 변환한다.
a = [int(x) for x in list(s.replace('\n', ''))]
# 5마디씩의 정수의 곱의 리스트로 변환하고, 그 중 최대값을 찾으면 된다.
b = [reduce(lambda x, y: x*y, a[i:i+5], 1) for i in range(0, 9995)]
print(max(b))숫자 문자의 시퀀스를 정수 리스트로 맵핑하고, 특정 범위의 곱으로 다시 맵핑하고 그 중에서 최대값을 구하는 문제는 함수형 스타일에서 생각하면 매우 간단한 문제이며, 이런 스타일의 계산 도구를 지원하는 언어에서는 간단하게 풀어낼 수 있는 문제이다..
보너스 : Swift 풀이
Swift에서는 이런 문제를 풀 때 상당히 번거롭고 귀찮았는데, Swift4가 되면서 멀티라인 문자열이 들어와서 넘나 좋은 것…
1000개의 문자열로 구분한 후에 이를 Int로 캐스팅하는 방법도 있는데, 이보다는 숫자로된 문자열에서 각 자리 숫자의 값을 따는 것으로는 아스키코드값을 이용하는 방법이 있다. 예를 들어 숫자 "0" 의 아스키코드값은 48이다. 이는 다음과 같이 확인해볼 수 있다.
let zero : String = "0"
print(zero.utf8.map{ Int($0) })
// 48아스키코드 내에서 숫자들은 모두 연속한 글자들이며, 0이 가장 빠르다. 따라서 0…9의 글자들은 모두 48…57의 값을 가질 것이다. (그렇다면 개행문자는 이 범위에 없기 때문에 자연스레 필터링되므로, 개행문자로 자르거나, 대체할 필요가 없다.) 참고로 Sequence에는 max() 라는 메소드가 있는데 비교 가능한 원소들 사이에서 최대값을 찾아준다. (단, max() -> Self.Element? 이다.)
// Swift 4.0
let s = """
73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450
"""
let vs = s.utf8.flatMap{ (48...57) ~= $0 ? Int($0) - 48 : nil }
let result = (0..<(vs.count)-5).map{ vs[$0..<$0+5].reduce(1, *) }.max()!
print(result)