Common Lisp 공부 - Google 입사 시험 문제

지난 번에 인터넷을 돌아다니다가 우연히 넥슨 입사 시험 문제를 발견하고는 이에 대해서 Common Lisp으로 재미삼아 풀어본 적이 있는데, 이번에는 Google 입사 시험 문제를 발견해버렸습니다. 문제 난이도로 보면 오히려 넥슨의 그것보다 좀 더 쉬워보이는 것 같기는 한데, 최적화를 할 수 있는 더 놀라운 방법이 함정으로 숨어 있는 것은 아닌지 의심되기도 합니다.

아래는 문제의 내용입니다. (이 문제의 출처는 http://ddingddong.egloos.com/788716입니다.)

양의 정수 n에 대해서 1과 n 사이에 1이 나오는 횟수를 나타내는 함수를 f(n)이라고 한다. 예를 들어 f(13)=6이다. f(n)=n이 되는 첫번째 양수는 1이다. 두번째 양수는 무엇인가?

이 문제에 대해서 제가 풀어본 내용은 다음과 같습니다.

(defun get-1-count-number-list (count)
  (do ((i 1 (1+ i))
       (cnt 0)
       (total 0)
       (nlist ()))
      ((= cnt count) (reverse nlist))
    (setq total
          (+ total
             (count #\1 (write-to-string i))))
    (if (= total i)
        (progn (incf cnt)
               (push total nlist)))))

문제의 출처에 Python으로 구현한 내용이 이미 있었지만, 일부러 그것을 보지 않고 Common Lisp으로 구현해보았습니다. 다 작성한 후 결과를 비교해보니 수를 문자로 바꾼 후 '1'의 개수를 세었다는 점에서 알고리즘이 거의 동일하더군요.

실행 결과는 다음 그림과 같습니다.



문제의 조건을 만족하는 수를 5개 정도 구해봤습니다만, 결국 원래 문제에서 요구하는 답은 199981이겠지요. 아무튼 답을 구해놓고 보니 처음 잠시 동안 암산으로 어찌 해보려던 제가 얼마나 무모했는지 알 수 있었습니다. :-$

제가 작성한 함수의 실행 시간과 사용된 메모리 공간을 확인해보기 위해서 일부러 time 함수를 사용했는데, Space 부분을 보시면 그 값이 엄청납니다. 결국 호기심이 발동한 저는 1의 개수를 산술적인 방법으로 세는 다른 함수를 만들어보았습니다. 모든 부분이 동일하고 단지 주어진 수에서 1의 개수를 세는 부분만 별도의 함수로 추가한 것입니다.

(defun get-1-count (num)
  (if (< num 10)
      (if (= num 1) 1 0)
      (+ (get-1-count (truncate (/ num 10)))
         (if (= (mod num 10) 1) 1 0))))

(defun get-1-count-number-list-2 (count)
  (do ((i 1 (1+ i))
       (cnt 0)
       (total 0)
       (nlist ()))
      ((= cnt count) (reverse nlist))
    (setq total
          (+ total
             (get-1-count i)))
    (if (= total i)
        (progn (incf cnt)
               (push total nlist))))

그리고, 이 함수에 대한 실행 결과입니다.



실행 시간은 좀 더 늘었지만, Space 사용량이 확연히 줄어든 것을 확인할 수 있습니다. get-1-count 함수를 recursion이 아닌 iteration 방식으로 작성했으면 더 줄었을지도 모릅니다. 하지만 귀찮아서 그만 하렵니다. 이 부분은 여러분 몫으로 남겨두죠. ;-)