문제 88 Symmetric Difference
(= (__ #{1 2 3 4 5 6} #{1 3 5 7}) #{2 4 6 7})
공통요소를 제거한 집합을 구하는 문제.
이건 이미 있을 것 같다. 그걸 쓰지 말라는 말은 없다.
(union에서 intersection을 diff) 혹은 (diff 두번한 것을 union)하는 것인데,
생각보다 길어질 것 같다.
직접 구현해보는 것도 연습이 될것 같다.
Clojure도 그렇고 Scala도 그렇고 함수형 프로그래밍 언어에서 특이한 점은 Set/Map 역시 '함수'라는 점이다. Set은 요소의 포함 여부를 알려주는 함수이며 Map은 키->값의 함수이다.
clojure.set 네임스페이스에 difference, union, intersection 등이 정의되어 있지만 Set이 함수라는 점을 이용하면 difference는 remove, union은 into, intersection은 filter라는 기본 함수로 구현 가능하다. 물론 이렇게 되면 into를 빼고 remove/filter의 결과가 Lazy sequence가 되기 때문에 set 함수로 다시 set을 만들어줘야 한다.
(union a b) == (into a b)
(intersection a b) == (set (filter a b))
(difference a b) == (set (remove b a))
into의 첫 인자만 set이면 되기 때문에 diff두번을 union하는 것이 Code Golf에는 유리해보인다. :-)
#(into (set (remove %1 %2)) (remove %2 %1))
100번 Least Common Multiple
(== (__ 5 3 7) 105)
(== (__ 3/4 1/6) 3/2)
최소공배수 문제지만 ratio를 처리할 수 있어야 한다.
그런데, 3/4 와 1/6 의 LCM이 왜 3/2일까? Wikipedia를 살펴보니 예가 나온다.
각 수를 소수(prime)의 지수(exponent)로 표시했을 때 LCM은 각 솟수별 지수의 큰값을 선택하면 된다.
3/4 = 2^-2 * 3^1
1/6 = 2^-1 * 3^-1
LCM(3/4,1/6) = 2^-1 * 3^1 = 3/2
그럼 이문제는 다시 각 수를 소수/지수 쌍으로 표현(소인수분해)하고, 이를 merge하면서 키(소수)가 충돌하면 큰 값을 선택하라는 얘긴가 싶다.
ratio를 소인수분해하려면 denom과numer를 각각 소인수분해한 다음 위(numer)에서 아래(denom)의 지수를 빼주면 된다.
(그런데, 이방법, 소인수분해 말고는 없을까? 말로만 적고보면 매우 귀찮아 보이는데.. 소수도 있어야 하고 말이지. ㅠ.ㅠ)
로제타코드의 소인수분해를 참고하여..
하려 했으나, 아무래도 소인수분해는 아닌거 같아서 더 기본적인 방법도 고려해보니,
유클리드 방법의 GCD가 ratio에도 적용되고, 그렇다면 LCM(a,b) = a*b / GCD 이므로 더 간단해질 것 같다.
(fn [a b]
(let [gcd (loop [a a b b]
(if (= a 0) b
(if (< a b)
(recur (- b a) a)
(recur (- a b) b))))]
(/ (* a b) gcd)))
그런데 주어진 문제에는 항이 여럿인 경우도 있다. GCD를 여러항에 대해 fold시키면 될듯.
(fn [& x]
(let [gcd (fn [a b]
(if (= a 0) b
(if (< a b)
(recur (- b a) a)
(recur (- a b) b))))]
(/ (apply * x) (reduce gcd x))))
한두타 더 줄이기 :-)
(fn [& x]
(let [g (fn [a b]
(cond (= a 0) b
(<= a b) (recur (- b a) a)
:else (recur b a)))]
(/ (apply * x) (reduce g x))))
마지막 쥐어짜기 인라인!
(fn [& x]
(/
(apply * x)
(reduce (fn [a b]
(cond (= a 0) b
(<= a b) (recur (- b a) a)
:else (recur b a)))
x)))
댓글 없음:
댓글 쓰기