변경이력

돌아가기
5 313개 문자 추가

2016/10/19 17:04

권용훈

**Ruby** 두가지로 풀었습니다. 첫째, combination. 둘째, 인형의 수가 아주 많아질 경우를 상정한 conditional combination구현. ```{.ruby} def lottery_game (n, sum), nums = 2.times.map { gets.split.map(&:to_i) } (1..n).flat_map {|i| nums.combination(i).select {|e| e.sum(0) == sum } } .map {|e| puts e.sort.join(' ') } end ``` **Test** ```{.ruby} $stdin = StringIO.new("10 50\n25 27 3 12 6 15 9 30 21 19\n") expect { lottery_game }.to output("6 19 25\n").to_stdout ``` **Output** ```{.ruby} lottery_game 10 50 25 27 3 12 6 15 9 30 21 19 ``` **Ruby - Conditional combination** combination 생성범위를 줄이기 위해서 두가지 조건을 줍니다. combination(depth+1)은 head, rest[1,1]로 생성하는데 둘의 합이 50보다 클 때만 생성합니다. combination(depth)는 head, rest[0]과 rest[1..-1]중 한개의 수로 생성하는데, 앞의 head와 rest[0]합이 sum보다 작거나 같을 때만 동작합니다. 범위가 극단적으로 줄어드므로 훨씬 빠릅니다. 재귀로 구현했는데 깔끔치는 않네요. ```{.ruby} def lottery_game_fast (n, sum), nums = 2.times.map { gets.split.map(&:to_i) } comb = ->head,rest,out do return out if (head + rest).empty? if rest.empty? head.sum == sum ? out << head : out else comb[head +[rest[0]], rest[1..-1], out] if head.sum(0) <= sum - rest[0] (head + rest[1..-1]).sum(0) >= sum ? comb[head, rest[1..-1], out] : out end end puts comb[[],nums,[]].map {|e| e.sort.join(' ') } end ``` **Performance** ```{.ruby} $stdin = StringIO.new("10 50\n25 27 3 12 6 15 9 30 21 19\n") puts Benchmark.realtime { lottery_game } 6 19 25 0.0011008729925379157 $stdin = StringIO.new("10 50\n25 27 3 12 6 15 9 30 21 19\n") puts Benchmark.realtime { lottery_game_fast } 6 19 25 0.000771850987803191 ```
**Ruby** 두가지로 풀었습니다. 첫째, combination. 둘째, 인형의 수가 아주 많아질 경우를 상정한 conditional combination구현. ```{.ruby} def lottery_game (n, sum), nums = 2.times.map { gets.split.map(&:to_i) } (1..n).flat_map {|i| nums.combination(i).select {|e| e.sum(0) == sum } } .map {|e| puts e.sort.join(' ') } end ``` **Test** ```{.ruby} $stdin = StringIO.new("10 50\n25 27 3 12 6 15 9 30 21 19\n") expect { lottery_game }.to output("6 19 25\n").to_stdout ``` **Output** ```{.ruby} lottery_game 10 50 25 27 3 12 6 15 9 30 21 19 ``` **Ruby - Conditional combination** combination 생성범위를 줄이기 위해서 두가지 조건을 줍니다. combination(depth+1)은 head, rest[1,1]로 생성하는데 둘의 합이 50보다 클 때만 생성합니다. combination(depth)는 head, rest[0]과 rest[1..-1]중 한개의 수로 생성하는데, 앞의 head와 rest[0]합이 sum보다 작거나 같을 때만 동작합니다. 범위가 극단적으로 줄어드므로 훨씬 빠릅니다. 재귀로 구현했는데 깔끔치는 않네요. ```{.ruby} def lottery_game_fast (n, sum), nums = 2.times.map { gets.split.map(&:to_i) } comb = ->head,rest,out do return out if (head + rest).empty? if rest.empty? head.sum == sum ? out << head : out else comb[head +[rest[0]], rest[1..-1], out] if head.sum(0) <= sum - rest[0] (head + rest[1..-1]).sum(0) >= sum ? comb[head, rest[1..-1], out] : out end end puts comb[[],nums,[]].map {|e| e.sort.join(' ') } end ``` **Performance** ```{.ruby} $stdin = StringIO.new("10 50\n25 27 3 12 6 15 9 30 21 19\n") puts Benchmark.realtime { lottery_game } 6 19 25 0.0011008729925379157 $stdin = StringIO.new("10 50\n25 27 3 12 6 15 9 30 21 19\n") puts Benchmark.realtime { lottery_game_fast } 6 19 25 0.000771850987803191 ```
4 4개 문자 추가 14개 문자 삭제

2016/10/19 17:00

권용훈

3 8개 문자 추가 1개 문자 삭제

2016/10/19 16:58

권용훈

2 4개 문자 추가

2016/10/19 16:58

권용훈

1 Original

2016/10/19 16:57

권용훈

코딩도장

코딩도장은 프로그래밍 문제풀이를 통해서 코딩 실력을 수련(Practice)하는 곳입니다.