프로젝트 오일러 8 @ntalbs' stuff

1000자리 숫자 안에서 이어지는 5자리 숫자의 곱 중 최대값은?
문제 자세히 보기: [국어]

1,000자리 숫자라고 하지만 1,000개의 숫자 리스트로 보는 편이 문제를 풀기에 더 좋을 것 같다. Clojure에서는 문자열도 시퀀스로 다룰 수 있으므로 bigint를 쓰기 보다는 문자열로 만들어 작업하는 게 더 편하다.

(def s
  (str "73167176531330624919225119674426574742355349194934"
       "96983520312774506326239578318016984801869478851843"
       "85861560789112949495459501737958331952853208805511"
       "12540698747158523863050715693290963295227443043557"
       "66896648950445244523161731856403098711121722383113"
       "62229893423380308135336276614282806444486645238749"
       "30358907296290491560440772390713810515859307960866"
       "70172427121883998797908792274921901699720888093776"
       "65727333001053367881220235421809751254540594752243"
       "52584907711670556013604839586446706324415722155397"
       "53697817977846174064955149290862569321978468622482"
       "83972241375657056057490261407972968652414535100474"
       "82166370484403199890008895243450658541227588666881"
       "16427171479924442928230863465674813919123162824586"
       "17866458359124566529476545682848912883142607690042"
       "24219022671055626321111109370544217506941658960408"
       "07198403850962455444362981230987879927244284909188"
       "84580156166097919133875499200524063689912560717606"
       "05886116467109405077541002256983155200055935729725"
       "71636269561882670428252483600823257530420752963450"))

일단 문자열을 만들어 놓으면 다음과 같이 시퀀스로 다룰 수 있다.

user=> s
"731671765313306249192251196744265..."
user=> (seq s)
(\7 \3 \1 \6 \7 \1 \7 \6 \5 \3 ...)

문자열 시퀀스의 각 요소는 Character이므로 이를 숫자(정수)로 바꿔주는 함수가 필요하다. 이 함수는 Character#digit를 이용해 간단히 작성할 수 있다.

(defn to-int [c] (Character/digit c 10))

to-int를 이용하면 다음과 같이 숫자 시퀀스를 얻을 수 있다.

user=> (map to-int s)
(7 3 1 6 7 1 7 6 5 3 ...)

이제 숫자 시퀀스에서 연속된 숫자 다섯 개씩 불러오면 되는데, partition 함수를 사용하면 쉽게 풀 수 있다. partition 함수는 n개의 아이템을 가지는 리스트의 지연 시퀀스를 리턴하며, step을 지정할 수 있다. 여기서는 step을 1로 지정하면 된다.

user=> (partition 5 1 *1)
((7 3 1 6 7) (3 1 6 7 1) (1 6 7 1 7) ...)

리스트의 시퀀스를 구했다. 각 리스트는 이어지는 다섯 개의 숫자를 나타낸다. 각 리스트의 요소를 곱한 다음 최대값을 구하면 되므로 다음과 같이 하면 답을 구할 수 있다.

(defn solve-kr []
  (->> s
       (map to-int)
       (partition 5 1)
       (map #(apply * %))
       (reduce max)))

결과는 다음과 같다.

p008=> (time (solve-kr))
"Elapsed time: 11.636357 msecs"
40???

업데이트

Project Euler 사이트 [Problem 8]을 보면 문제가 살짝 바뀌어 있다. 처음에는 인접한 다섯 개의 숫자를 곱하는 것이었는데 지금은 13개의 숫자를 곱한 최대값을 구하라고 되어 있다. 그런다고 문제가 어려워지는 것은 아니다. 다섯 개씩 자르던 부분을 13개씩 자르도록 바꿔주기만 하면 된다.

(defn solve-en []
  (->> s
       (map to-int)
       (partition 13 1)
       (map #(apply * %))
       (reduce max)))

p008=> (time (solve-en))
"Elapsed time: 8.101594 msecs"
23514???000

참고

프로젝트 오일러 8 풀이 소스 코드