こんにちは！今回はグループ分けをするためのアルゴリズムについて解説します。問題はLeetCodeの2938です。
この問題は無理やり解こうとすれば解けてしまいますが、美しく、エレガントに解きたい、がそれができなかったので反省として記事を書くことにしました。
問題
問題はLeetCode2938です。1と0からなる文字列について１は全て右側に、０は全て左側に移動させた場合、合計で最低何回移動させればよいか求めます。
解説
s="1001"の場合を考えます。この場合、一番左側にある1を右に移動させる必要があり、その移動回数は2回です。移動後はs="0011"となりグループ分けができました。
次にs="1011001"を考えていきます。1は合計で4個あるため、グループ分けをした後はs="0001111"になるはずです。
様々な移動方法があると思いますが、無駄な動きをしないという条件下では、どの移動方法も同じ移動回数になっています。そのため、ここでは左から0があるかを確認していき、あったら0を左側へと移動させる方法でグループ分けをします。
例えば、左から2番目は0であるため、その左側にある1と入れ替えてs="0111001"にします。これで移動回数が1になりました。その後、左から5番目に0があるため、その左側にある連続する1よりも左側に適切に移動させます。このとき、s="0011101"であり、合計の移動回数は4です。
この方法で行うメリットは、合計の移動回数が左から移動していく中で遭遇した"1"の回数を、0と遭遇したときのみ足し合わせた合計と等しいことです。
再度、s="1011001"で考えます。また、sのインデックスをidx(初期値0)とするとidx=1のとき”0″と遭遇します。このとき、今までに”1″と遭遇した回数は1回です。同様に、idx=4のとき再び”0″と遭遇し、今までに”1″と遭遇した回数は3回であり、idx=5のときも”1″との遭遇回数は3回となります。したがって、それらの和1+3+3=7回がs="1011001"の解であることがわかりました。
以下はAcceptedされたプログラムです。
def minimumSteps(self, s: str) -> int:
n = len(s)
white = 0
i = 0
ans = 0
while i < n:
if s[i] == "0":
ans += white
if s[i] == "1":
white += 1
i += 1
return ans
ansが合計の移動回数を表しています。
まとめ
今回は、グループ分けをするための移動回数を求める問題に取り組んでみました。
答えを出すだけであれば無理やり解くこともできますが、できる限りスマートに解きたいと思う問題でした。
最後まで読んでいただきありがとうございます。お疲れ様でした。
コメント