변경이력

돌아가기
7 146개 문자 추가 956개 문자 삭제

2016/11/29 05:25

권용훈

**Ruby** 중복(x,y위치)을 갖는 컴팩트 트리를 대칭이 되도록 오른쪽에서 살며시 당기는 방식. 중복지점을 찾고 중복노드 둘의 공통부모를 찾은 뒤 공통부모 포함 우측 노드가 대칭이 되도록 이동/반복. 2번 풀이에서 Node 구조 수정(부모노드 검색 요건) minimize(당기기) 추가. ```{.ruby} add = ->par,node do par ? (node.y = par.y + 1; node.u = par.id) : (return node) chd = node.val < par.val ? par.l : par.r chd ? add[chd, node] : (node.val < par.val ? par.l = node : par.r = node) par end calc_x = ->node,par do left_x = par.x + (node == par.l ? -1 : 1) if par node.x = (node.l ? node.l.x + 1 : par&.x > 0 ? left_x : 1) node.r.x = node.x + 1 if node.r end minimize = ->nodes,vst do find_dups = -> { nodes.group_by {|e| [e.x, e.y]}.select {|_,v| v.size > 1}.first } while dups = find_dups[] do d1u, d2u = dups[1].map {|e| parent_id = nodes[e.u] } d1u, d2u = nodes[d1u.u], nodes[d2u.u] until d1u == d2u d1u.x += 1 vst.map.with_index {|e,i| e.x += 2 if i > vst.index {|e| e.id == d1u.id } } end end layout = ->tree_str=gets.chop,visits=[] do Node = Struct.new(:id, :val, :x, :y, :l, :r, :u) nodes = tree_str.chars.map.with_index {|c,i| Node.new(i, c, 0, 1)} btree = nodes.reduce(&add) trav = ->node,par=nil do trav[node.l, node] if node.l calc_x[node, par] visits << node trav[node.r, node] if node.r end trav[btree] minimize[nodes, visits] puts visits.map {|e| [e.val, e.x, e.y].join(" ") } end ``` **Test** ```{.ruby} minimized_tree1 = "a 1 4\n" + "c 2 3\n" + "d 2 5\n" + "e 3 4\n" + "g 4 5\n" + "k 3 2\n" + "m 4 3\n" + "n 5 1\n" + "p 6 3\n" + "q 7 4\n" + "u 7 2\n" expect{ layout["nkcmaedgupq"] }.to output(minimized_tree1).to_stdout minimized_tree2 = "a 1 3\n" + "b 1 6\n" + "c 2 5\n" + "d 3 4\n" + "e 2 2\n" + "f 2 4\n" + "g 3 5\n" + "h 4 6\n" + "i 4 3\n" + "j 5 5\n" + "k 6 6\n" + "l 7 7\n" + "m 7 9\n" + "n 8 8\n" + "o 6 4\n" + "p 7 5\n" + "q 7 1\n" + "r 9 3\n" + "s 9 5\n" + "t 10 4\n" + "u 11 5\n" + "v 12 6\n" + "w 11 2\n" + "x 12 4\n" + "y 13 3\n" + "z 14 4\n" expect{ layout["qwertyuiopasdfghjklzxcvbnm"] }.to output(minimized_tree2).to_stdout ``` **Output** ```{.ruby} cmd > layout.call nkcmaedgupq a 1 4 c 2 3 d 2 5 e 3 4 g 4 5 k 3 2 m 4 3 n 5 1 p 6 3 q 7 4 u 7 2 cmd > layout.call qwertyuiopasdfghjklzxcvbnm a 1 3 b 1 6 c 2 5 d 3 4 e 2 2 f 2 4 g 3 5 h 4 6 i 4 3 j 5 5 k 6 6 l 7 7 m 7 9 n 8 8 o 6 4 p 7 5 q 7 1 r 9 3 s 9 5 t 10 4 u 11 5 v 12 6 w 11 2 x 12 4 y 13 3 z 14 4``` **Output** ```{.ruby} cmd > layout.call nkcmaedgupq a 1 4 c 2 3 d 2 5 e 3 4 g 4 5 k 3 2 m 4 3 n 5 1 p 6 3 q 7 4 u 7 2 ```
**Ruby** 중복(x,y위치)을 갖는 컴팩트 트리를 대칭이 되도록 오른쪽에서 살며시 당기는 방식. 중복지점을 찾고 중복노드 둘의 공통부모를 찾은 뒤 공통부모 포함 우측 노드가 대칭이 되도록 이동/반복. 2번 풀이에서 Node 구조 수정(부모노드 검색 요건) minimize(당기기) 추가. ```{.ruby} add = ->par,node do par ? (node.y = par.y + 1; node.u = par.id) : (return node) chd = node.val < par.val ? par.l : par.r chd ? add[chd, node] : (node.val < par.val ? par.l = node : par.r = node) par end calc_x = ->node,par do left_x = par.x + (node == par.l ? -1 : 1) if par node.x = (node.l ? node.l.x + 1 : par&.x > 0 ? left_x : 1) node.r.x = node.x + 1 if node.r end minimize = ->nodes,vst do find_dups = -> { nodes.group_by {|e| [e.x, e.y]}.select {|_,v| v.size > 1}.first } while dups = find_dups[] do d1u, d2u = dups[1].map {|e| parent_id = nodes[e.u] } d1u, d2u = nodes[d1u.u], nodes[d2u.u] until d1u == d2u d1u.x += 1 vst.map.with_index {|e,i| e.x += 2 if i > vst.index {|e| e.id == d1u.id } } end end layout = ->tree_str=gets.chop,visits=[] do Node = Struct.new(:id, :val, :x, :y, :l, :r, :u) nodes = tree_str.chars.map.with_index {|c,i| Node.new(i, c, 0, 1)} btree = nodes.reduce(&add) trav = ->node,par=nil do trav[node.l, node] if node.l calc_x[node, par] visits << node trav[node.r, node] if node.r end trav[btree] minimize[nodes, visits] puts visits.map {|e| [e.val, e.x, e.y].join(" ") } end ``` **Test** ```{.ruby} minimized_tree1 = "a 1 4\n" + "c 2 3\n" + "d 2 5\n" + "e 3 4\n" + "g 4 5\n" + "k 3 2\n" + "m 4 3\n" + "n 5 1\n" + "p 6 3\n" + "q 7 4\n" + "u 7 2\n" expect{ layout["nkcmaedgupq"] }.to output(minimized_tree1).to_stdout minimized_tree2 = "a 1 3\n" + "b 1 6\n" + "c 2 5\n" + "d 3 4\n" + "e 2 2\n" + "f 2 4\n" + "g 3 5\n" + "h 4 6\n" + "i 4 3\n" + "j 5 5\n" + "k 6 6\n" + "l 7 7\n" + "m 7 9\n" + "n 8 8\n" + "o 6 4\n" + "p 7 5\n" + "q 7 1\n" + "r 9 3\n" + "s 9 5\n" + "t 10 4\n" + "u 11 5\n" + "v 12 6\n" + "w 11 2\n" + "x 12 4\n" + "y 13 3\n" + "z 14 4\n" expect{ layout["qwertyuiopasdfghjklzxcvbnm"] }.to output(minimized_tree2).to_stdout ``` **Output** ```{.ruby} cmd > layout.call nkcmaedgupq a 1 4 c 2 3 d 2 5 e 3 4 g 4 5 k 3 2 m 4 3 n 5 1 p 6 3 q 7 4 u 7 2 cmd > layout.call qwertyuiopasdfghjklzxcvbnm a 1 3 b 1 6 c 2 5 d 3 4 e 2 2 f 2 4 g 3 5 h 4 6 i 4 3 j 5 5 k 6 6 l 7 7 m 7 9 n 8 8 o 6 4 p 7 5 q 7 1 r 9 3 s 9 5 t 10 4 u 11 5 v 12 6 w 11 2 x 12 4 y 13 3 z 14 4``` **Output** ```{.ruby} cmd > layout.call nkcmaedgupq a 1 4 c 2 3 d 2 5 e 3 4 g 4 5 k 3 2 m 4 3 n 5 1 p 6 3 q 7 4 u 7 2 ```
6 1개 문자 삭제

2016/11/29 04:28

권용훈

5 373개 문자 추가

2016/11/29 04:27

권용훈

4 441개 문자 추가

2016/11/29 04:25

권용훈

3 14개 문자 추가 15개 문자 삭제

2016/11/29 04:14

권용훈

2 59개 문자 추가 5개 문자 삭제

2016/11/28 03:37

권용훈

1 Original

2016/11/28 03:25

권용훈

코딩도장

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