CodeIQのチケットゴブル問題を解いてみた
スペーストーキー問題のリベンジ。
頭の中で考えたアルゴリズムをコードに落としました。
コード
可読性ってナンデスカ…。
思いついた解法
あまりにもコードだと分かりにくすぎるので、以下でかるーくコメントしていきます。
チケットを読み込み
データをパッと見でうるう日があったりと、どんな罠があるか分からなかったので出国日も帰国日も文字列にしちゃいました。
a=[] b=[] tickets.split(/\n/).each {|t| t = t.split(/\s|-/); if (t.length >= 3) then t[1] = t[1].split(/\//) from = t[1][0].rjust(2,"0") + t[1][1].rjust(2,"0") t[2] = t[2].split(/\//) to = t[2][0].rjust(2,"0") + t[2][1].rjust(2,"0") a.push({"name" => t[0],"from" => from,"to" => to}) end }
チケットを帰国日降順ソート
a = a.sort {|x, y| y["to"] <=> x["to"] }
チケットを先頭から順に、対象チケットとチケット数最大となる組み合わせを保持(b)
def getMaxTickets(target, tickets) max = [] tickets.each {|t| if (nodup(t[0], target) && max.length < t.length) then max = t end } return max end a.each{|t| c=[] c.push(t) c += getMaxTickets(t,b) b.push(c) }
チケット数で降順ソート、最大チケット数とチケット(国名アルファベット順)を出力
b = b.sort {|x, y| y.size <=> x.size } d = b[0].sort {|x, y| x['name'] <=> y['name'] } print d.size d.each{|s| print " " + s['name']}
解を出したあとに悩んだこと
出国日昇順ソートで検算したら別解が出てきた
→目で見てもプランの中で交換できそうなチケットがあるのを確認。問題文に条件が書かれていたので安心しました。
あなた 「 もしも 、 枚数が同じ複数のプランがあった場合にはどうしましょうか 」
依頼者 「 プランはひとつだけ作っていただければ結構です 」
また、このタイミングで「国名アルファベット順」に気づいて慌てて直しました。
感想
徐々に頭にアルゴリズムの基礎を擦り込めている気がします。問題の難易度のせいもあるかもしれませんが試行錯誤の回数が減ってきました。
最適な解法の選択とコードへの落とし込みを徐々に早く出来るよう引き続き問題を解いていこうと思います。