Pythonで連続する数字の出現回数をカウントする方法：itertools.groupbyの活用

問題概要

数字のみで構成された文字列 s が与えられます。同じ数字は複数回出現することがあります。ここで、「どの数字が何回連続して出現したか」を表すペア（数字, 出現回数）のリストを返すプログラムを作成することを考えます。

この問題を効率的に解くには、Python標準ライブラリ itertools に含まれる groupby() 関数を利用すると便利です。groupby() はイテレータオブジェクトを返し、各要素は「キー（この場合は数字）」と「グループオブジェクト」のタプルとして取得できます。各グループに含まれる要素数を数えることで、連続出現回数を簡単に求められます。

入力例と出力例

例えば、入力が s = "11522226551" の場合、出力は [(1, 2), (5, 1), (2, 4), (6, 1), (5, 2), (1, 1)] となります。これは、先頭から順に「1」が2回連続し、次に「5」が1回、その後に「2」が4回連続して現れる、といったように文字列を走査した結果です。

解法のアルゴリズム

以下の手順で問題を解きます。

• groupby() を文字列 s に対して呼び出し、イテレータ it を取得します
• 結果を格納するための空のリスト ret を用意します
• it 内の各ペア（digit, gp）について以下を繰り返します
  • 数字 digit（整数に変換）と、グループ gp をリスト化した際の長さ（＝連続出現回数）をタプルとして ret に追加します
• 最終的に ret を返します

なお、この手法の計算量は文字列の長さを n とすると O(n) であり、非常に効率的です。

実装例（Pythonコード）

実際の実装例を見てみましょう。

from itertools import groupby

def solve(s):
    it = groupby(s)
    ret = []
    for digit, gp in it:
        ret.append((int(digit), len(list(gp))))
    return ret

s = "11522226551"
print(solve(s))

入力

"11522226551"

出力

[(1, 2), (5, 1), (2, 4), (6, 1), (5, 2), (1, 1)]

まとめ

itertools.groupby() を使うことで、連続する同一要素のまとまりを簡潔に検出できます。ランレングス圧縮（RLE）のようなデータ圧縮処理や、時系列データの連続パターン解析など、さまざまな場面で応用できるテクニックなので、ぜひ覚えておきましょう。