はじめに naive な解法を説明します。問題文の正しい括弧列の定義に従うと、以下に説明する手順でこの問題の入力に正しい答えを返すことができます。

• \(S\) に () が存在する間、\(S\) から () を取り除く。
• 操作後に \(S\) が空文字列になれば答えは Yes, そうでない場合は No である。

しかしこのアルゴリズムは最悪計算量が \(\mathrm{O}(N^2)\) となり実行時間制限を超過してしまいます。
計算量を改善する方法としてスタックを利用する方法があります。具体的には、以下の手順で説明されるアルゴリズムによって () を前から順に検出することができます。

• スタック \(t\) がある。はじめ \(t\) は空である。
• \(i = 1, 2, \dots, N\) についてこの順に次の操作を行う。
  • スタックの先頭が ( かつ \(S[i] =\) ) である場合、スタックの先頭を取り除く。
  • そうでない場合、スタックの先頭に \(S[i]\) を追加する。
• 上の操作を終了した時点でスタックが空ならば Yes, そうでないならば No である。

このアルゴリズムは計算量はスタックに要素を追加した回数で抑えられ、これは高々 \(N\) 回です。よってこのアルゴリズムは \(\mathrm{O}(N)\) で動作して、十分高速です。