아래는 문제의 내용입니다. (이 문제의 출처는 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'의 개수를 세었다는 점에서 알고리즘이 거의 동일하더군요.
실행 결과는 다음 그림과 같습니다.
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg_2E5JhfhRT337J5GVVq-jhMME1SUg_J2xUC-PAr2yjZfdgf8qu5KaqCQ7Z63Y-4OAnqGIscwxkUWmxUjeOfK2sOYhEiR45AkKDxZmMtUmiEnlj4pxIZ81KH-4N_QXPyeMZ1h90zWNmmE/s400/1-count.png)
문제의 조건을 만족하는 수를 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))))
그리고, 이 함수에 대한 실행 결과입니다.
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhcUUn19TPylll6Z1JqqFehZZMbIjKlfJsJsdKxkm-SR95y0dn25FJopk-Mb6AyWc5GR3XEAdkv0xxwsxm8VGzhommCu02YebGCvQdMy11wxvYek-AoLTByKii-intaRm8IEjdcIkl7VWc/s400/1-count2.png)
실행 시간은 좀 더 늘었지만, Space 사용량이 확연히 줄어든 것을 확인할 수 있습니다. get-1-count 함수를 recursion이 아닌 iteration 방식으로 작성했으면 더 줄었을지도 모릅니다. 하지만 귀찮아서 그만 하렵니다. 이 부분은 여러분 몫으로 남겨두죠. ;-)