각 자릿수의 팩토리얼을 더했을 때 자기 자신이 되는 수들의 합은?
먼저 각 자릿수의 팩토리얼을 더한 값을 구하는 함수는 다음과 같이 작성할 수 있다.
(defn- sum-of-fact [n]
(->> (digits n)
(map factorial)
(reduce +)))
이 함수를 이용하면 각 자릿수의 팩토리얼을 더한 값이 자기 자신이 되는지 확인하는 함수를 다음과 같이 작성할 수 있다.
(defn check [n]
(= n (sum-of-fact n)))
이 함수가 true를 리턴하는 수를 찾으면 된다. 그러나 수는 무한하기 때문에 모두 조사할 수 없다. 조사할 수의 범위를 어디까지 할지 결정하는 것이 진짜 문제다.
상한을 결정하는 방법은 문제 30에서 사용했던 방법과 비슷하다. 7자리 숫자 중 가장 큰 수는 9,999,999인데, 이 수의 각 자릿수의 팩토리얼을 더하면 2,540,160로 7자리 숫자가 된다.
그러나 8자리 숫자 중 가장 큰 수인 99,999,999의 각 자릿수의 팩토리얼을 더하면 2,903,040로 8자리 숫자를 만들지 못한다.
8자리 숫자 중 가장 큰 수로도 각 자릿수의 팩토리얼을 더했을 때 8자리 숫자를 만들지 못한다면 그보다 작은 8자리 숫자는 고려할 필요도 없다. 따라서 문제의 조건을 만족하는 수는 7자리 이하의 수여야 함을 알 수 있다. 그리고 7자리 숫자 중 가장 큰 수의 각 자릿수의 팩토리얼을 더해 만든 수가 2,540,160이므로 이 값을 상한으로 할 수 있다.
(defn solve []
(->> (range 11 (inc 2540160))
(filter check)
(apply +)))
실행 결과는 다음과 같다.
p034=> (time (solve)) "Elapsed time: 6633.732546 msecs" 407??
답을 구하기는 하지만 너무 시간이 오래 걸린다. 좀더 빠르게 할 수 없을까?
개선할 만한 부분이 한 곳 보인다. 이 문제에서는 각 자릿수의 팩토리얼을 구하므로 항상 0~9의 숫자에 대해서만 팩토리얼을 구할 텐데, 이 값을 항상 반복해서 계산하고 있다. 어차피 값이 아홉 개 뿐이므로 다음과 같이 팩토리얼 값을 미리 계산해 놓은 함수를 만들면 어떨까?
(defn factorial [n]
(case n
0 1
1 1
2 2
3 6
4 24
5 120
6 720
7 5040
8 40320
9 362880))
팩토리얼 함수를 위와 같이 바꾼 다음 풀이를 실행하면 답을 구하는 데 걸리는 시간이 절반 이하로 줄어든다.
p034=> (time (solve)) "Elapsed time: 2922.186357 msecs" 407??
그러나 여전히 3초 가까이 시간이 걸린다. 더 줄일 수 없을까?
맨 처음 구현한 sum-of-fact는 직관적이긴 하지만 효율적이지는 못하다. digits 함수도 시퀀스를 리턴하고, map도 시퀀스를 리턴하므로 단순한 정수 계산보다는 훨씬 무겁다. 거의 2백50만 개의 수를 조사해야 하므로 이 부분을 좀더 가볍게 만들면 성능 향상이 클 것이다. 중간에 시퀀스를 생성하지 않고 다음과 같이 정수 계산만 하도록 구현하면 함수를 훨씬 가볍게 할 수 있다.
(defn- sum-of-fact [n]
(loop [n n acc 0]
(if (< 0 n)
(recur (quot n 10) (+ acc (factorial (rem n 10))))
acc)))
0!은 1이므로 (sum-of-fact 0)은 1을 리턴해야 하지만 이 구현은 0을 리턴할 것이다. 그러나 문제에서는 0에 대해 고려하지 않아도 되므로 문제 없이 사용할 수 있다.
p034=> (time (solve)) "Elapsed time: 388.065762 msecs" 407??
이 정도면 만족스러운 결과라 할 수 있다. 처음 결과보다 20배 정도 빨라졌다.