SICP 연습문제 2.62 친절한 풀이

문제

차례 매긴 리스트로 집합을 표현하여, 그 계산 단계가 $Θ(n)$으로 자라나도록 union-set 프로시저를 구현하라.

문제로 부터 얻은 것

인자로 받은 set1과 set2가 null?인지부터 검사하고 let을 사용해야 한다는 것을 다시 또 다시 배웠습니다.
자칫 let 안에서 nil값을 계산해서 오류가 생길 수 있기 때문입니다.

문제풀이

책에 나와있는 intersetcion-set을 참고하면 구현하는 것이 그렇게 어렵지는 않습니다. 확실히 정렬이 되어 있는 집합은 알고리즘을 짤때도 생각할 거리가 많이 적었습니다.

(define (union-set set1 set2)
  (cond ((null? set1) set2)
        ((null? set2) set1)
        (else
         (let ((x1 (car set1))
               (x2 (car set2)))
           (cond ((null? set1) set2)
                 ((null? set2) set1)
                 ((= x1 x2) (cons x1
                            (union-set (cdr set1) (cdr set2))))
                 ((> x1 x2) (cons x2
                            (union-set set1 (cdr set2))))
                 ((< x1 x2) (cons x1
                            (union-set set2 (cdr set1)))))))))

(define s1 '(1 2 3 4 5 6))
(define s2 '(1 4 6 7 8 9))

(union-set s1 s2)

읽어주셔서 감사합니다.