[競プロ用]ランレングス圧縮まとめ - Qiita

いつ使うのか 与えられる文字列で連続する回数・個数に着目する問題。 何がいいのか 画像圧縮などに利用される手法。膨大なデータを可逆性を損なわずに圧縮できる。 ただし、元データよりも必ずしもデータ量が少なくなるとは限らない。連続する構造の少ないデータでは逆に増加することもある。 どうするのか 同じ文字が何回繰り返されるかの文字と数字の組み合わせで表す。 テンプレート from itertools import groupby # RUN LENGTH ENCODING str -> list(tuple()) # example) "aabbbbaaca" -> [('a', 2), ('b', 4), ('a', 2), ('c', 1), ('a', 1)] def runLengthEncode(S: str) -> "List[tuple(str, int)]": grouped =