NoSyu의 주저리주저리 :: SICP Exercise 연습문제 2.61

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

어느 값과 합치는 adjoin-set 프로시저를 만드는 문제입니다.

방법은 책에 나오는 element-of-set?과 비슷합니다.

잘 되는군요.^^

방법은 다음과 같습니다.

들어온 값과 set의 첫 번째 원소가 같다면 중복을 허용하지 않기에 set을 내놓습니다.

들어온 값이 set의 첫 번째 원소보다 작다면 set 앞에 붙이면 됩니다.

들어온 값이 set의 첫 번째 원소보다 크다면 다음 원소를 봐야합니다.

하지만 다음 원소가 없을 경우 들어온 값이 set의 마지막이 되어야 합니다.

이번에는 깔끔하게 잘 만든 듯싶습니다.^^

들어온 값이 set의 모든 원소보다 큰 최악의 경우가 아니라면

매우 빠르게 끝낼 수 있으니 성능 향상이 되어 좋습니다.^^

참조

해럴드 애빌슨, 김재우 역, <컴퓨터 프로그램의 구조와 해석>, 인사이트, 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)))))))

; answer
(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))))

; execute
(define setA (list 2 4 6))
setA
(newline)
(adjoin-set 1 setA)
(adjoin-set 2 setA)
(adjoin-set 3 setA)
(adjoin-set 4 setA)
(adjoin-set 5 setA)
(adjoin-set 6 setA)
(adjoin-set 7 setA)

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