search
LoginSignup
0

More than 1 year has passed since last update.

posted at

updated at

Rubyの「宇宙船演算子」を再定義して AtCoder ABC219C を解く

AtCoder の ABC219C の問題は以下のリンクから参照下さい。

簡単にいうと、アルファベットの順番を替えた上で、複数の文字列を辞書順にソートして出力するという問題です。

じつはこれ、とても Ruby らしい簡潔な解法が存在するので、まずはそちらを説明します。

Ruby
x = gets.chomp
n = gets.to_i
strs = n.times.map { gets.chomp }

puts strs.sort_by { _1.tr(x, "a-z") }

xは新しいアルファベットの順番、strsはソートすべき文字列の入った配列で、sort_byを使って、解いている部分は1行で書けています。かかる時間もかなり速いです。

本題

さて、Array#sortは配列の中身が文字列の場合、暗黙にいわゆる「宇宙船演算子」、つまりString#<=>を使って辞書順にソートします。では、これを再定義してやれば、ただのArray#sortでいけるのではないかという、変態的発想をもちました。

Ruby
x = gets.chomp
n = gets.to_i
strs = n.times.map { gets.chomp }

$table = x.each_char.map.with_index { |c, i| [c, i] }.to_h

class String
  def <=>(other)
    l = [length, other.length].min
    (0...l).each do |i|
      a = self[i]
      b = other[i]
      if a != b
        return $table[a] <=> $table[b]
      end
    end
    length <=> other.length
  end
end

puts strs.sort

「辞書順」の定義は、問題文の「辞書順とは?」にあるアルゴリズムをそのまま実装しました。グローバル変数なぞ使って、美しくないコードですね。時間も上の簡潔な解法に比べ、10倍ほどかかっています。メリットはまるでないのですが、オープンクラスを使い、組み込みの比較用のメソッドを再定義するという、極め付きの動的言語である Ruby 以外ではちょっと不可能な解法ではないでしょうか。実際、ソートはただのArray#sortで済んでいますね。お粗末様でした。

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
What you can do with signing up
0