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

잘 되는군요.^^

방법은 다음과 같습니다.

set1을 고정시킨 후 set2에 차례대로 접근하여 set1에 같은 원소가 있는지 확인합니다.

만약 같은 원소가 있다면 해당 원소를 set1에 붙이지 아니하고,

같은 원소가 없다면 해당 원소를 set1에 붙이면 됩니다.

이를 생각해보니 adjoin-set 프로시저를 쓰면 될 듯싶어 뒤에 고쳤습니다.

이 프로시저를 살펴보니 element-of-set? 프로시저를 n²번 정도 부르네요.

따라서 Θ(n²)인 듯싶습니다.

참조

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

(define true (= 0 0))
(define false (= 0 1))
; section 2.3.3
(define (element-of-set? x set)
  (cond ((null? set) false)
        ((equal? x (car set)) true)
        (else (element-of-set? x (cdr set)))))
(define (adjoin-set x set)
  (if (element-of-set? x set)
      set
      (cons x set)))
(define (intersection-set set1 set2)
  (cond ((or (null? set1) (null? set2)) '())
        ((element-of-set? (car set1) set2)
         (cons (car set1)
               (intersection-set (cdr set1) set2)))
        (else (intersection-set (cdr set1) set2))))

; answer
(define (union-set set1 set2)
  (cond ((null? set1) set2)
        ((null? set2) set1)
;        ((element-of-set? (car set2) set1)
;         (union-set set1 (cdr set2)))
;        (else (union-set (cons (car set2) set1) (cdr set2)))))
        (else
         (union-set (adjoin-set (car set2) 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 대한민국 라이선스에 따라 이용하실 수 있습니다.