【競プロ】Rubyでラングレス圧縮を実装する

メモです。

計算量 n
計算量 2*n
ラングレス圧縮を使用した問題

計算量 n

# 入力例：100010111001010
s = gets.chomp

n = s.size
cnt = 1
a = []
n.times do |i|
  if s[i] == s[i+1]
    cnt += 1
  else
    a << [s[i].to_i, cnt] # 文字列の場合はto_iは外す
    cnt = 1
  end
end

#=> [[1, 1], [0, 3], [1, 1], [0, 1], [1, 3], [0, 2], [1, 1], [0, 1], [1, 1], [0, 1]]

計算量 2*n

# 入力例：100010111001010
s = gets.chomp

s.chars.slice_when{ |e, c| e != c }.map{ |e| [e[0].to_i, e.size] } # 文字列の場合はto_iは外す
#=> [[1, 1], [0, 3], [1, 1], [0, 1], [1, 3], [0, 2], [1, 1], [0, 1], [1, 1], [0, 1]]

こっちのほうがスマート。
ループを２回分回していますが、あまり影響無いのでこちらをメインで使いそう。