myRuby.net

이전 연습: 3n+1 문제  다음 연습: 유쾌한 점퍼 (Jolly Jumper)

연습은 계속되어야 한다. 아직은 개발 환경에 익숙치 않으니 어렵지 않은 문제로 하나 더.

문제

http://www.programming-challenges.com/pg.php?page=downloadproblem&probid=110103&format=html

여행 중 일단 개개인이 지출을 하고, 나중에 모두 공평할 수 있도록 금액을 주고 받는다고 하는데, 이 때 최소로 주고 받을려면 얼마면 되겠냐는 문제다. 딱 떨어지지 않을 때 적절하게 분배하는 것이 핵심이다.

풀이

1. def minimum_transfer(*vals)
     vals = vals.map{|v| (v*100).to_i }.sort{|x, y| y <=> x} 
     len = vals.length
    
     to_pay = [vals.sum / len] * len             # 공평하게 나누고
     (vals.sum % len).times{|i| to_pay[i] += 1 } # 나머지는 이미 많이 지불한 사람들이 부담
    
     vals.map_with_index{|v, i| (v - to_pay[i]).abs}.sum / 200.0
   end

• 전체 소스코드: http://github.com/deepblue/snippets/tree/master/chalenge/trip/trip.rb

1. : normalize-input ( seq -- seq )
     [ 100 * >integer ] map natural-sort reverse ;
   
   ! y개의 1로 이뤄진 길이 x의 array를 만든다
   : (bit-array) ( x y -- seq )
     1 <array> swap 0 pad-right ;
   
   : to-pay ( seq -- seq )
     [ sum ] [ length ] bi [ /mod ] keep
     rot [ <array> ] 2keep
     drop rot (bit-array)
     v+ ;
   
   : minimum_transfer ( seq -- x )
     normalize-input [ to-pay ] keep v-
     [ abs ] map sum 200.0 / ;

• 전체 소스코드: http://github.com/deepblue/snippets/tree/master/chalenge/trip/trip.factor

1. init(X) -> lists:sort( fun(A,B) -> A>B end,
     lists:map( fun(N) -> trunc(N*100) end, X) ).
    
   to_pay(X) ->
     Avr = lists:sum(X) div length(X),
     Rem = lists:sum(X) rem length(X),
     lists:duplicate(Rem, Avr + 1) ++ lists:duplicate(length(X) - Rem, Avr).
    
   subtract(A, B) -> subtract(A, B, []).
   subtract([A|H], [B|T], L) -> subtract(H, T, L ++ [abs(A-B)]);
   subtract([], [], L) -> L.
   
   minimum_transfer(X) -> Input = init(X),
     lists:sum(subtract(Input, to_pay(Input))) / 200.0.

• 전체 소스코드: http://github.com/deepblue/snippets/tree/master/chalenge/trip/trip.erl

후기

• Factor의 to_pay 워드를 좀 이해하기 쉽게 만들고 싶었는데, 쉽지 않다. 나중에 연습이 더 되면 다시 풀어봐야겠다.
• erlang의 리스트 뺄셈은 표준 라이브러리로도 할 수 있을 것 같은데, 방법을 못 찾겠다. 
• 그래서 약간씩 아쉬운 코드들.