4clojure | 써노로그

http://www.4clojure.com/problem/30

Difficulty: Easy
Topics: seqs

	(= (apply str (__ “Leeeeeerrroyyy”)) “Leroy”)
	(= (__ [1 1 2 3 3 2 2 3]) ‘(1 2 3 2 3))
	(= (__ [[1 2] [1 2] [3 4] [1 2]]) ‘([1 2] [3 4] [1 2]))

내 풀이 방법..

#(reduce (fn [s a] (if (not= (last s) a) (conj s a) s)) [] %)

입력할 요소(a)를 확인한 후
추가대상이면 현재 시퀀스(s)에 추가하고,
아니면 시퀀스(s)를 그대로 유지

reduce 를 활용한 단순한(?) 방법이다.

일단 머리에 떠오르는대로 알고리즘을 구현한 것인데, 다른 사람들의 솔루션을 확인하고 대충격.

;; maximental's solution:
#(map last (partition-by list %))

;; daowen's solution:
#(map first (partition-by identity %))

partition-by 라는 충격적인 함수가 있었던 것.

콜렉션의 함수를 인자로 받아서 콜렉션의 각 요소에 적용한 다음, 다른 결과가 나오는 요소들끼리 콜렉션으로 묶어준다. 위 문제의 경우 partition-by 을 적용한 다음 하나씩만 뽑아내면(first 또는 last) 끝.

4clojure #26을 풀 때도 그러했지만, ‘클로저가 제공하는 함수들과 그 관점을 얼마나 익숙하게 떠올리고 활용할 수 있는가’ 가 간단한 문제해결에 다가설 수 있는 비결인 것 같다.

http://www.4clojure.com/problem/26

Difficulty: Easy
Topics: Fibonacci seqs

Write a function which returns the first X fibonacci numbers.

	(= (__ 3) ‘(1 1 2))
	(= (__ 6) ‘(1 1 2 3 5 8))
	(= (__ 8) ‘(1 1 2 3 5 8 13 21))

분명 난이도가 ‘쉬움 (Easy)’인데.. 아직까지도 사고의 전환이 잘 안되어서인지 몰라도 그리 쉽게 풀리지 않았다..

일단 나는 이렇게 풀었다.

(fn [n] (nth (iterate #(conj % (apply + (take-last 2 %))) [1]) (dec n)))

아이디어는 다음과 같다.

벡터에서 마지막 두 숫자를 잡아서 더하고 기존 벡터에 이어붙이는(conj) 함수를 만들자.
```
#(conj % (apply + (take-last 2 %)))
```
1번의 과정은 [1] 에서 시작하도록 하되, 한 번 수행한 결과를 다시 그 함수에 집어넣자.
```
(iterate (1번결과함수) [1])
```
2번의 수행 횟수를 지정하기 위해 다시 함수로 감싸자 (수행 횟수는 이미 [1]로 시작하므로 1회 줄여서 입력)
```
(fn [n] (nth (2번결과함수) [dec n]))
```

처음에는 iterate 함수의 존재를 몰랐기 때문에 2번 과정에서 시간이 많이 걸렸다. reduce 의 경우 아이템 갯수가 정해진 벡터내에서 동작하므로 이 문제를 해결하려면 재귀함수를 별도로 만들어 적용해야할 것 같은데, 더 간단한 방법이 있지 않을까 꽤나 고민을 하다가 iterate 함수가 정확히 그런 용도로 사용되는 것을 발견했다 (ClojureDocs – iterate).

다음으로, iterate 적용 후에 3번을 수행하는 과정에서도 #(func %) 과 같은 방식의 익명함수를 시도했는데(코드를 조금이라도 더 줄이기 위해), 에러가 나서 실행을 할 수가 없었다. iterate 에 입력되는 함수에서 인자(%)를 받고 있기는 하지만 이미 iterate 자체가 콜렉션을 리턴하므로 바깥쪽에서 감싸더라도 문제가 없을 것이라 생각했는데 에러가 발생해서 결국 3번과 같은 방식으로 감싸야 했다 (이유는 정확히 모르겠다).

문제를 풀고나면 확인할 수 있는 다른 사람의 풀이도 살펴보자.

; maximental's solution
(fn [n] 
  (take n
        (map first 
             (iterate (fn [[f s]] [s (+ f s)]) 
                      [1 1]))))

; daowen's solution:
#(take % ((fn fib [x y] (lazy-seq (cons x (fib y (+ x y))))) 1 1))

maximental 의 경우 ClojureDocs의 iterate에 있는 예제와 동일한 방식을 사용한다. 두 숫자를 포함하는 벡터 [f s] 에서 뒷쪽 숫자인 s 와, f 와 s 를 더한 숫자로 구성된 벡터를 만들어내는 과정을 반복하면서 각 벡터로부터 첫번째 숫자만을 골라낸다 (map first) .

daowen의 경우는 처음에 생각해보려했던 재귀적인 방식을 사용한다. 재귀 아이디어를 제외하면 이 방식에서의 키 팁은 lazy-seq 를 사용하는 것이다. 그냥 seq 를 사용해버리면 재귀호출에 의해 overflow 가 발생해버린다.

Tag: 4clojure

Compress a Sequence – 4Clojure #30

Fibonacci Sequence – 4Clojure #26