문제 26, 팬 케이크, Stacks of Flapjacks, PC/UVa ID : 110402/120

PC/UVa ID : 110402/120

이 포스트를 만든 목적

• 생각 절차, 푼 방법, 고민거리 등을 기록하기 위해서 만들었다.
  

이 포스트의 준비물

• firefox4 beta10
  
• eclipse 3.6.1 + vrapper
  
• lua 5.1.4

참조 문헌

• 스티븐 스키에나, 미구엘 레비야 저. Programming Challenges: 알고리즘 트레이닝 북. 서환수 역.
  Springer. 한빛미디어 초판 2쇄 2004.12.05. (문제 26, 팬 케이크, Stacks of Flapjacks, page 121)
  

참고 링크

•  http://www.algorithmist.com/index.php/UVa_120 - 문제 원문

이야기

주방장이 팬 케이크(Flapjack)를 여러장 만들어서, 손님에게 대접했다. 그런데 손님이 팬 케이크가 쌓여 있는게 뒤죽박죽이라 이상해 보인다고 한다. 돈 받고 판 음식이니 고객의 요청대로 뒤죽박죽 쌓인 팬 케이크를 크기가 큰 순을 맨 밑에 두어 정렬 시키려고 한다. 그런데 매번 생각해야 되니, 프로그래머인 나에게 정렬 시키는 방법을 알려 주는 프로그램을 만들어 달라고 요청했다.

프로그램의 입력/출력

1. 프로그램은 한 라인에 팬케이크의 지름을 여러개 입력을 받는다. 각각의 팬케이크는 스페이스로 구분된다.
   예) 1 2 3 4 5
   
2. 입력 받은 팬케이크는 입력된 순서로 쌓여 있는데, 쌓여있는 팬케이크의 제일 위쪽이 입력된 숫자의 첫번째이다. 그러므로 마지막에 입력된 숫자가 쌓여 있는 팬케이크의 제일 밑에 있는 것이다.
   
   
3. 이를 숫자로 표현하면 제일 밑이 1, 제일 위가 팬케이크의 총 갯수가 된다.
   
4. 입력이 끝나면, 원래 쌓여진 펜케이크 순서를 출력하고, 다음 라인에 뒤집는 방법을 출력한다.
   
   
5. 공백이 입력 될때까지 1 ~ 4 를 반복한다. 자세한 것은 사진 참조
   

맛보기 사진

맛보기 코드
-- PC/UVa : 110401/10041 -- http://ikpil.com -- 2011.01.30 ------------------------------------------------------------------------------- function fn_stack_input() local input_txt = io.read("*line") -- parsing local tb_stack = { } for d in input_txt:gmatch("%d+") do tb_stack[#tb_stack + 1] = d + 0 end if 0 == #tb_stack then return nil else return tb_stack end end function fn_stack_flip(tb_stack, n) local index = n - 1 for i = 1, #tb_stack - n do table.insert(tb_stack, i, tb_stack[#tb_stack - index]) table.remove(tb_stack, #tb_stack - index) end end function fn_stack_sort(tb_stack) local tb_fliping_history = {} for last_index = #tb_stack, 1, -1 do -- 정렬되지 않은 팬케이크 범위에서, -- 최고 큰 팬케이크을 가진 인덱스를 찾는다. local max_value_index = last_index for i = 1, last_index do if tb_stack[max_value_index] < tb_stack[i] then max_value_index = i end end -- 정렬되지 않은 팬케이크 범위에서, -- 최고 큰 팬케이이크를 가진 인덱스가 정상 위치가 아닐 경우 -- 팬 케이크를 뒤집어야 한다. if max_value_index < last_index then -- 정렬 시킬 팬케이크가 첫번째 자리에 없을 경우 -- 첫번째 자리로 이동 시켜, 뒤집을 준비를 한다. -- 이는 첫번째 자리에 있어야, 뒤집었을 때, 정렬 되기 때문이다. local flip_index = 0 if 1 < max_value_index then flip_index = #tb_stack - max_value_index + 1 tb_fliping_history[#tb_fliping_history + 1] = flip_index fn_stack_flip(tb_stack, flip_index) end -- 펜케이크를 뒤집어 정렬 시킨다. flip_index = #tb_stack - last_index + 1 tb_fliping_history[#tb_fliping_history + 1] = flip_index fn_stack_flip(tb_stack, flip_index) end end tb_fliping_history[#tb_fliping_history + 1] = 0 return tb_fliping_history end function main() while true do local tb_stack = fn_stack_input() if nil == tb_stack then break end print(table.concat(tb_stack, " ")) local tb_fliping_history = fn_stack_sort(tb_stack) print(table.concat(tb_fliping_history, " ")) io.flush() end end main() --[[ package.path = package.path .. ";C:\\Users\\ikpil\\Desktop\\programming_challenges\\?.lua" require "lunit" test_case = lunit:new() test_case.tb_sorted = { 1, 2, 3, 4, 5 } function test_case:test_flip() local tb_stack = { 5, 4, 3, 2, 1 } fn_stack_flip(tb_stack, 1) for i = 1, 5 do lunit:assert_true(i == tb_stack[i]) end local tb_stack = { 5, 1, 2, 3, 4 } fn_stack_flip(tb_stack, 1) fn_stack_flip(tb_stack, 2) for i = 1, 5 do lunit:assert_true(i == tb_stack[i]) end end function test_case:test_sort() local tb_stack = { 5, 4, 3, 2, 1 } fn_stack_sort(tb_stack) for i = 1, #tb_stack do lunit:assert_true(tb_stack[i] == self.tb_sorted[i]) end end function test_case:test_sort2() local tb_stack = { 1, 2, 3, 4, 5 } fn_stack_sort(tb_stack) for i = 1, #tb_stack do lunit:assert_true(tb_stack[i] == self.tb_sorted[i]) end end function test_case:test_sort3() local tb_stack = { 5, 1, 2, 3, 4 } fn_stack_sort(tb_stack) for i = 1, #tb_stack do lunit:assert_true(tb_stack[i] == self.tb_sorted[i]) end end function test_case:test_sort4() local tb_stack = { 3, 1, 2, 5, 4 } fn_stack_sort(tb_stack) for i = 1, #tb_stack do lunit:assert_true(tb_stack[i] == self.tb_sorted[i]) end end lunit:run() --]]

여담

• 테스트 주도 개발 방법론을 사용해 봤다. 꽤 괜찮다. 버그도 많이 잡을수 있었고..
  
• 루아이기 때문에 테이블을 사용했고, 테이블을 사용했기 때문에 0번 인덱스를 사용할 수 없어 1번으로 보정했다.
  
• 개발 순서를 1. 뒤집는 함수 2. 필요한 인자 얻는 로직 3. 입력 순으로 하면 편할 것이다.
  
  
• 내 방식데로 다 만든 후에 답지를 봤는데, 내가 고민했던 부분을 없애 버린 로직(어디 부터 어디까지 뒤집을 것인가? 를 찾는 로직)을 보고 감동 받았다.  맛보기 코드로 만든 것은 이러한 영향을 반영한 것이다.

:wq!