Pythonで括弧の各深さごとの文字数をカウントするプログラムの作成方法

文字列 s が与えられます。この文字列は「X」「(」「)」の3種類の文字のみで構成されており、括弧は必ずバランスが取れていて、その間に「X」が含まれています。また、括弧は再帰的にネストしている場合もあります。

この課題では、最も浅い深さから最も深い深さへ向かって、各括弧の深さごとに「X」の個数を求めます。

入力例と出力例

たとえば、入力が s = "(XXX(X(XX))XX)" の場合、出力は [5, 1, 2] になります。

• 深さ0（最も外側の括弧の中）には「X」が5個
• 深さ1には「X」が1個
• 深さ2（最も内側の括弧の中）には「X」が2個

解き方のアプローチ

この問題は、次の手順で解くことができます。

• depth := -1 … 現在の深さを表す変数を初期化します
• out := 空のリスト … 各深さの結果を格納するリストを用意します
• 文字列 s の各文字 c について、以下を繰り返します
  • c が「(」の場合 → depth を +1 します
  • c が「)」の場合 → depth を -1 します
  • depth が out のサイズと一致したら → out の末尾に 0 を追加します（新しい深さに対応するため）
  • c が「X」の場合 → out[depth] を +1 してカウントします
• 最後に out を返します

ポイント：なぜ depth を -1 から始めるのか

depth を -1 で初期化しておくことで、最初の「(」に出会った時点で depth が 0 になり、最も外側の括弧の内側が「深さ0」として正しく扱われます。また、「depth == len(out)」という条件判定により、初めて到達した深さに対して自動的にカウンター用の要素が追加される仕組みになっています。

実装例

理解を深めるために、実際のPythonコードを見てみましょう。

def solve(s):
    depth = -1
    out = []

    for c in s:
        if c == "(":
            depth += 1
        elif c == ")":
            depth -= 1

        if depth == len(out):
            out.append(0)

        if c == "X":
            out[depth] += 1
    return out

s = "(XXX(X(XX))XX)"
print(solve(s))

入力

"(XXX(X(XX))XX)"

出力

[5, 1, 2]

計算量について

このアルゴリズムは文字列を一度だけ走査するため、時間計算量は O(n)、結果リストの分だけメモリを使用するため空間計算量も O(n) となります。スタック構造を明示的に使わずに済む、非常にシンプルで効率的な解法です。