【Ruby基礎】AtCoder Beginner Contest 019 B – 高橋くんと文字列圧縮

INDEX

■はじめに

Rubyの基礎的な問題をたくさん解くことで基本的な考え方やメソッドの使い方を定着させたい。
基本的にはAtCoderというプログラミングコンテスト（競技プログラミング）の過去問を使う。（AtCoderは難易度が分かれており、難易度の低いA問題かB問題を解いていく）

（5/23時点の方針）
メソッドの切り分け方や値の受け渡しを練習するために、コード長の短さについては気にせずに書くことにする。

（2022/10/17時点の方針）
しばらくはB問題を小さい番号の方からやっていく。たまにA問題もやるかも。

高橋くんはある文字列 s を持っています。文字列を短く表現することに興味のある高橋くんは、以下の圧縮方法を試してみることにしました。

aabbbaadという文字列に上記の圧縮方法を適用すると

以上より、a2b3a2d1 を得ることができます。

あなたには文字列 s が与えられるので、上記の方法で圧縮された文字列を求めるプログラムを、高橋くんの代わりに書いてください。

入力は以下の形式で標準入力から与えられる。

s から作られた圧縮された文字列を標準出力に出力せよ。
末尾の改行を忘れないこと。

tallyを使うかな？
…だめだ、tallyしちゃうと例えばaabbbaadの時に前半のaと後半のaがまとめて足されて4つのaになってしまう。

初めから1文字ずつ見ていって、「同じ文字が並んだら数を足し上げる、違う文字になったら次に行く」みたいな処理をやらないといけないのかな…。

もしくは、なんらかの方法で同じ文字ごとで区切られた配列にして、要素ごとの文字数を出すことができればできるか？

後者ができればシンプルなんだけど、「同じ文字ごとで区切られた配列にする」方法が全然わからない…。

わからなすぎて、可能な範囲でググってみた。
どうやら正規表現を使う方法があるっぽい…？

正規表現の後方参照というのを使うと良さそう。あとはgsubとかscanあたりが使えそうな気がするのだけど、わからない…。

s = gets.chomp

m = s.gsub(/(.)\1+/) { |matched| "#{$1}#{matched.size}"}
puts m

上記は不正解なのだけど、途中経過として書いておく。
意味合いとしては下記。

(.)\1+というのは
- .は、「改行以外の１文字」を示すメタ文字
- \1は、後方参照。
- つまり、これで「同じ文字の連続」という意味になる。
gsubすることで同じ文字が連続している部分をマッチさせる
{ }を使って、先述の同じ文字の連続でマッチした部分をブロックパラメーターとして以下を回していく
- $1は、置換文字列（＝連続していた文字が何か）
- matched.sizeは、何回連続しているのかの数

かなりギリギリの理解度だけど、どうにかわかったような気はする。

ただし上述の通りこのコードだと正解にはならない。
なぜかと言うと、連続しない文字がある場合に数字（1文字だけなので1）が付かないから。
例えば入力がaabbbaadの場合、正しい出力はa2b3a2d1なんだけど、上記のコードだと最後の1が無いa2b3a2dになってしまう。

ということは、また正規表現を使って「アルファベット+数字というセットにならない場合にはアルファベットの次に1を入れる」という処理をすれば正解になるか…？

…だめだ〜わからない。
右往左往して下記を作ったけど、1文字だけが並んだ場合に破綻する。

s = gets
m = s.gsub(/(.)\1+/) {|m| "#{$1}#{m.size}"}
g = m.gsub(/[a-z]+[^0-9]/) {|m| "#{m[0]}1#{m[1]}"}

puts g

時間がかかりすぎているのでギブアップ。
他の方の回答を見る。

結構惜しいところまで行っていたけど、結局gsubや正規表現への理解が足りてなくて辿り着けなかったということか。

自分の書いたものに近くて正答なのは例えば下記。

s=gets.chomp
puts s.gsub(/(.)\1*/) {|t| t[0]+t.size.to_s}

+と*の違い！なるほど。。。
https://userweb.mnet.ne.jp/nakama/

下記で通る。

s=gets.chomp
puts s.gsub(/(.)\1*/) { |m| "#{$1}#{m.size}"}

公式リファレンスを見る訓練。

今回は完全にギブアップだった。
正規表現はまだまだ全然使いこなせていないので、今日触れることができて良かった。