이 문제는 차례대로 표현된 리스트를 받아

그 합집합을 구하는 union-set 프로시저를 만드는 문제입니다.

방법은 책에 나오는 intersection-set 프로시저와 비슷합니다.

잘 되는군요.^^

intersection-set 프로시저와 달리 서로 크든 작든 같든 간에 합쳐야 합니다.

그리고 합친 후 그 다음 것을 기준으로 찾기에

서로 각자의 원소를 한 번씩만 살펴보면 됩니다.

따라서 계산 단계가 Θ(n)입니다.

참조

해럴드 애빌슨, 김재우 역, <컴퓨터 프로그램의 구조와 해석>, 인사이트, 2007, pp. 201

(define true (= 0 0))
(define false (= 0 1))

; section 2.3.3
(define (element-of-set? x set)
  (cond ((null? set) false)
        ((= x (car set)) true)
        ((< x (car set)) false)
        (else (element-of-set? x (cdr set)))))
(define (intersection-set set1 set2)
  (if (or (null? set1) (null? set2))
      '()
      (let ((x1 (car set1)) (x2 (car set2)))
        (cond ((= x1 x2)
               (cons x1
                     (intersection-set (cdr set1)
                                       (cdr set2))))
              ((< x1 x2)
               (intersection-set (cdr set1) set2))
              ((< x2 x1)
               (intersection-set set1 (cdr set2)))))))

; exercise 2.61
(define (adjoin-set x set)
  (cond ((equal? x (car set)) set)
        ((< (car set) x)
         (if (null? (cdr set))
             (list (car set) x)
             (cons (car set) (adjoin-set x (cdr set)))))
        ((< x (car set)) (cons x set))))

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

; execute
(define setA (list 1 2 3))
(define setB (list 2 3 4 5))
setA
setB
(newline)
(intersection-set setA setB)
(union-set setA setB)

크리에이티브 커먼즈 라이선스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이선스에 따라 이용하실 수 있습니다.