概要

正しく対応の取れた括弧列が与えられたとき、括弧の入れ子の最大の深さを求める問題です。

考察

重要な気づき

括弧の深さは、現在位置までに出現した ( の数から ) の数を引いた値で表現できます。

例えば ((())) を左から順に見ていくと： - ( → 深さ 1 - (( → 深さ 2 - ((( → 深さ 3（ここが最大） - ((() → 深さ 2 - (()) → 深さ 1 - ()) → 深さ 0

つまり、( が出てくるたびに深さが1増え、) が出てくるたびに深さが1減ります。

素朴なアプローチとの比較

この問題はスタックを使って解くこともできます。( をスタックに積み、) が来たらスタックから取り出す方法です。スタックの最大サイズが答えになります。

しかし、今回の問題では スタックに何を積んだかを記憶する必要がない（すべて ( なので）ため、スタックのサイズだけを整数変数で管理すれば十分です。これにより、空間計算量を \(O(N)\) から \(O(1)\) に削減できます。

アルゴリズム

1. 変数 current_depth（現在の深さ）と max_depth（最大の深さ）を \(0\) で初期化する
2. 文字列 \(S\) を先頭から1文字ずつ見ていく
   • ( の場合：current_depth を \(1\) 増やし、max_depth を更新
   • ) の場合：current_depth を \(1\) 減らす
3. 最終的な max_depth が答え

具体例

入力が (()()) の場合：

位置	文字	current_depth	max_depth
0	(	1	1
1	(	2	2
2	)	1	2
3	(	2	2
4	)	1	2
5	)	0	2

答えは \(2\) となります。

計算量

• 時間計算量: \(O(|S|)\)
  • 文字列を1回走査するだけ
• 空間計算量: \(O(1)\)
  • 変数を2つ使うだけで、入力サイズに依存しない

実装のポイント

• max_depth の更新は ( を読んだ直後に行う必要があります。current_depth が増えた瞬間が、新しい深さに到達したタイミングだからです。

• 正しく対応の取れた括弧列であることが保証されているため、current_depth が負になるケースや、最終的に \(0\) にならないケースを考慮する必要はありません。

  ソースコード

S = input()

max_depth = 0
current_depth = 0

for c in S:
    if c == '(':
        current_depth += 1
        max_depth = max(max_depth, current_depth)
    else:  # c == ')'
        current_depth -= 1

print(max_depth)

---

この解説は claude4.5opus によって生成されました。