Common Lisp 공부 - 넥슨 입사 문제 1 번 풀이

요즘 공부 좀 해보려고 이것 저것 찔러보고 있는 중입니다. 아무 것도 하지 않고 계속 시간만 보내다가는 정말 머리가 굳어버릴 것만 같은 위기감을 느꼈기 때문이죠. 새해도 되고 했으니 설사 '작심삼일(作心三日)'이 될지언정 시도조차 하지 않아서야 사람이라고 하겠습니까.. 쩝..

아무튼, 찔러보는 것 중에서 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