오일러 프로젝트 8

오일러 프로젝트 8 번 문제는 1000개의 연속된 숫자에서, 연속한 5개의 부분열의 곱을 계산하여 그 중 가장 큰 값을 찾는 문제이다. 

다음은 연속된 1000자리 숫자입니다 (읽기 좋게 50자리씩 잘라놓음)

73167176531330624919225119674426574742355349194934
 96983520312774506326239578318016984801869478851843
 85861560789112949495459501737958331952853208805511
 12540698747158523863050715693290963295227443043557
 66896648950445244523161731856403098711121722383113
 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개의 숫자가 일렬로 늘어서 있고, 이 중에서 연속하는 다섯개의 숫자의 곱 중에서 가장 큰 값을 구하는 것이다.

  1. 가장 앞의 숫자 5개는 0번~4번 인덱스 범위를 갖는다.
  2. 1번에서 5번, 2번에서 6번… 이렇게 5개 숫자에 대해서 반복하면서
  3. 각 숫자를 정수로 변환하고 곱하는 값으로 변환한 후
  4. 그 중에서 가장 큰 값을 구하면 된다.

여기서 요구되는 스킬은 다음과 같다.

  • 여러 줄로 나눠서 쓴 문자열을 하나의 숫자 시퀀스로 변환하기
  • 숫자시퀀스를 정수의 리스트로 변환하기
  • 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)