日々精進

新しく学んだことを書き留めていきます

プログラミングコンテストチャレンジブック演習「best cow line」

今回のお題はこちら。


本の回答例で先頭と末尾の文字のどちらをtに移すか判定するところをforループを使って処理していましたが、再帰を使って書いてみました。
こっちの方がすっきりしてていいですね。
あーでもInputの文字数が2000文字までだから、コールスタックが最大1000積まれることになりますね。オーバーフローしそう。。

s = "ACDBCB" #input
$t = ""

def isFirstCharToElim?(str)
  if str.length <= 1 then return true
  elsif str[0] < str[-1] then return true
  elsif str[0] > str[-1] then return false
  else isFirstCharToElim?(str[1..-2])
  end
end

s.length.times do |i|
  if isFirstCharToElim?(s)
    $t = $t + s[0].chr
    s = s[1..-1]
  else
    $t = $t + s[-1].chr
    s = s[0..-2]
  end
end

puts $t