환상과 현실의 거리 :: Synap Soft 2009년도 입사문제 6번 수정

Scheme2009/06/20 10:25

Synap Soft 2009년도 입사문제 6번 수정

Q6 – 막대 자르기
동수는 길이가 같은 여러 개의 막대를 잘라서 길이가 다양한 막대 여러 개로 만들었다. 이제 동수는 그 잘라놓은 막대들을 원래대로 돌려놓고 싶어한다. 그러나 원래 막대가 몇 개였는지 그 길이가 얼마였는지 잊어버렸다. 원래 막대의 가능한 길이 중 가장 작은 값을 찾는 프로그램을 작성해서 그를 도와주자. 모든 길이는 0보다 커야 한다.

*각 라인에 원래 막대의 가능한 가장 작은 길이를 출력한다.
*구성이 불가능한 경우 -1을 출력(즉, 모든 막대기를 합친 값이 가장작은 길이라면 원래 하나인 것이 된다.)

#lang scheme
(require test-engine/scheme-tests)

(define (enum-divisor items-sum)
  (define (iter n result)
    (cond [(> (* n 2) items-sum) result]
          [(= (remainder items-sum n) 0) (iter (+ n 1) (append result (list n)))]
          [else (iter (+ n 1) result)]))
  (iter 1 null))

(define (subsets s)
  (if (null? s)
      (list null)
      (let ([rest (subsets (cdr s))])
        (append rest (map (λ(x)(cons (car s) x)) rest)))))

(define (equal-length-bars? bars len)
  (let ([dict (filter (λ(x)(= (foldr + 0 x) len)) 
                      (remove-duplicates (subsets bars)))])
    (cond [(null? bars) true]
          [(null? dict) false]
          [else (ormap (λ(x)(equal-length-bars? (remove-atom x bars) len))
                       dict)])))

(define (remove-atom v items)
  (if (null? v)
      items
      (remove-atom (cdr v) (remove (car v) items))))

(define (shortest-bar-if-restore bars)
  (define (iter checks)
    (cond [(null? checks) -1]
          [(equal-length-bars? bars (car checks)) (car checks)]
          [else (iter (cdr checks))]))
  (iter (filter (λ(x)(>= x (argmax (λ(x)x) bars)))
                (enum-divisor (foldr + 0 bars) ))))

(check-expect true (equal-length-bars? '(1 1 2 2 1 3) 5))
(check-expect false (equal-length-bars? '(1 1 2 2 1 3 1) 5))
(check-expect false (equal-length-bars? '(1 1 1 1 1 1) 5))

(check-expect 1 (shortest-bar-if-restore '(1 1 1 1 1 1 1)))
(check-expect 5 (shortest-bar-if-restore '(2 2 1 3 3 5 4)))
(check-expect 6 (shortest-bar-if-restore '(5 2 1 5 2 1 5 2 1)))
(check-expect 5 (shortest-bar-if-restore '(1 2 3 4)))
(check-expect 5 (shortest-bar-if-restore '(5 4 3 2 1)))
(check-expect 8 (shortest-bar-if-restore '(3 2 4 5 2)))
(check-expect 5 (shortest-bar-if-restore '(1 1 2 2 1 3)))
(check-expect 5 (shortest-bar-if-restore '(5 4 3 2 1)))
(check-expect 10 (shortest-bar-if-restore '(5 3 2 4 4 2)))
(check-expect -1 (shortest-bar-if-restore '(7 4 3 2 1)))
(check-expect 14 (shortest-bar-if-restore '(3 3 3 2 3 3 3 3 2 3)))
(check-expect 12 (shortest-bar-if-restore '(9 9 7 7 4 4 4 4 4 3 2 1 1 1)))

(test)

Output:

ようこそ DrScheme, バージョン 4.1.5 [3m].
言語: Module; memory limit: 256 megabytes.
All 15 tests passed!
>

여전히 어렵다 ㅠㅠ 여튼 품.
*부연설명
*퍼포먼스따위는 전혀 생각지 않고 오로지 가독성만을 최고로 유지한 코드.
[(= checksum (foldr + 0 bars)) -1]

(마지막 종료조건은 그냥 리스트의 길이를 따지는것이 좋음)
*이코드에서 가장 복잡한 부분은 ormap 연산부분. ormap은 다음과 같이 따로 구현할 수 있다.

(define (orrmap pred? items)
  (cond [(null? items) #f]
        [(pred? (car items)) #t]
        [else (orrmap pred? (cdr items))]))

(display (orrmap even? '(1 3 5 7 9 11 13 15)))
(newline)
(display (orrmap even? '(1 3 5 7 8 9 11 13 15)))

Output:

1
2

#f
#t

orrmap으로 대체해도 똑같이 작동함. 즉, 모든 노드를 다 가보는 재귀처리.

*답이 모든 수의 합의 약수중에 있다는 말을 들음.. 그런 성질을 이용하면 프로세스를 좀 더 줄일 수 있다.
*해봤는데 생각보다 큰 차이는 나지 않았다. 원리를 몰라 코드는 안바꿈.

*재수정. 생각해보니 답이 모든 수의 합의 약수중에 있는것이 당연하다.