아무튼, 찔러보는 것 중에서 Common Lisp이 있는데, 애자일 이야기에서 우연히 접하게 된 넥슨 입사 문제 중 1 번을 시험 삼아 구현해보았습니다. 공부를 막 시작한지라 구현 내용이 다소 비효율적이고 어눌할 수도 있으니 너그러이 이해해주세요. ;-)
문제 내용은 다음과 같습니다.
어떤 자연수 n이 있을 때, d(n)을 n의 각 자릿수 숫자들과 n 자신을 더한 숫자라고 정의하자. 예를 들어 d(91) = 9 + 1 + 91 = 101 이다. 이 때, n을 d(n)의 제네레이터(generator)라고 한다. 위의 예에서 91은 101의 제네레이터이다. 어떤 숫자들은 하나 이상의 제네레이터를 가지고 있는데, 101의 제네레이터는 91 뿐 아니라 100도 있다. 그런데 반대로, 제네레이터가 없는 숫자들도 있으며, 이런 숫자를 인도의 수학자 Kaprekar가 셀프 넘버(self-number)라 이름 붙였다. 예를 들어 1,3,5,7,9,20,31 은 셀프 넘버 들이다.
1 이상이고 5000 보다 작은 모든 셀프 넘버들의 합을 구하라.
풀이 내용은 다음과 같습니다.
;; 주어진 수의 각 자리수의 합을 구한다.
;; (예, 352 -> 3 + 5 + 2)
(defun sum-of-each-digit (x)
(if (< x 10)
x
(+ (mod x 10)
(sum-of-each-digit (truncate (/ x 10))))))
;; 주어진 수의 generated number를 구한다.
(defun get-generated-number (x)
(+ x (sum-of-each-digit x)))
;; 주어진 범위 내에 존재하는 generated number의 list를 구한다.
;; 범위: (x <= r < y)
(defun get-generated-number-list (x y)
(do ((i x (1+ i))
(gnum (get-generated-number x)
(get-generated-number i))
(gnums ()))
((or (>= gnum y) (>= i y))
(remove-duplicates (sort gnums #'<)))
(push gnum gnums)))
;; 주어진 범위 내의 정수 list를 구한다.
;; 범위: (x <= r < y)
(defun make-number-range-list (x y)
(do ((i x (1+ i))
(rnums ()))
((>= i y) (reverse rnums))
(push i rnums)))
;; 주어진 범위 내에 존재하는 Self Number의 list를 구한다.
;; 범위: (x <= r < y)
(defun get-self-number-list (x y)
(set-difference
(make-number-range-list x y)
(get-generated-number-list x y)))
;; 주어진 범위 내에 존재하는 Self Number의 합을 구한다.
;; 범위: (x <= r < y)
(defun sum-of-self-number-list (x y)
(apply #'+ (get-self-number-list x y)))
;; 1부터 5000 사이에 존재하는 Self Number들의 합을 구한다.
(sum-of-self-number-list 1 5000)
결과: 1227365
