カッコ列対応問題の詳細解析

問題: 対応の取れているカッコ列 (())()) において、どの位置のカッコ同士が対応しているかを見つける

1. 入力データの可視化

入力文字列の構造
(())())
1234567

各文字の位置を1-indexedで表示しています。文字列の長さは7文字です。

2. アルゴリズムの処理フロー

1. 左から右へ
文字を走査
2. 開きカッコ'('
→スタックに位置を追加
3. 閉じカッコ')'
→スタックから取得
4. ペアを作成
→結果配列に追加

3. ステップバイステップの詳細実行トレース

位置
文字
スタック状態
作成されるペア / 処理内容
1
(
[1]
開きカッコなので位置1をスタックにプッシュ
2
(
[1, 2]
開きカッコなので位置2をスタックにプッシュ
3
)
[1]
ペア作成: [2, 3] - 位置2をポップして位置3と組み合わせ
4
)
[]
ペア作成: [1, 4] - 位置1をポップして位置4と組み合わせ
5
(
[5]
開きカッコなので位置5をスタックにプッシュ
6
)
[]
ペア作成: [5, 6] - 位置5をポップして位置6と組み合わせ

4. スタック操作の可視化

各ステップでのスタック状態

位置1: '(' 処理後

1
スタック

位置2: '(' 処理後

2
1
スタック

位置3: ')' 処理後

1
スタック
ペア: [2, 3]

位置4: ')' 処理後

スタック(空)
ペア: [1, 4]

位置5: '(' 処理後

5
スタック

位置6: ')' 処理後

スタック(空)
ペア: [5, 6]

5. 発見されたペアの一覧

処理順序でのペア
[2, 3]
[1, 4]
[5, 6]

スタックの性質により、内側のカッコから順にペアが作成されます。

6. ソート処理の詳細解析

ソート条件: max(li, ri) < max(li+1, ri+1)

各ペアの最大値計算:

[2, 3]
max(2, 3) = 3
[1, 4]
max(1, 4) = 4
[5, 6]
max(5, 6) = 6
↓ ソート実行 ↓

ソート後の順序:

1位: [2, 3] (max=3)
2位: [1, 4] (max=4)
3位: [5, 6] (max=6)

7. 最終出力

最終結果
2 3
1 4
5 6

8. 計算量とメモリ使用量の分析

時間計算量: O(n log n)
• スタック操作: O(n) • ソート処理: O(n log n)
空間計算量: O(n)
• スタック: 最大O(n/2) • ペア配列: O(n/2)

メモリ使用量の詳細

スタック:
最悪の場合 n/2 要素
(すべて開きカッコの場合)
ペア配列:
正確に n/2 要素
(カッコのペア数)
入力文字列:
n 文字
(最大200,000文字)

9. アルゴリズムの正当性

なぜこのアルゴリズムが正しく動作するのか：

  1. スタックの性質: LIFO (Last In, First Out) により、最も内側のカッコから順に処理される
  2. 対応関係の保証: 正しいカッコ列では、各閉じカッコに対応する開きカッコが必ずスタックの最上位にある
  3. ソート条件: 出力順序の制約を満たすため、各ペアの最大位置で昇順ソート
  4. 1-indexed変換: 問題の要求に合わせて、配列のインデックス(0-indexed)を位置(1-indexed)に変換