yutasの競技プログラミング勉強帖

競技プログラミングの問題についての解説記事を主に書いています。

E - 括弧列 / 第13回 アルゴリズム実技検定 (PAST13)

PAST13 AtCoder C++ アルゴリズム実技検定 PAST 競技プログラミング

問題

(, ) からなる文字列のうち、連続する () を消すことを0回以上繰り返すことにより空文字列になる文字列のことを、正しい括弧列と呼ぶ。

  • (), (()), (()())() は正しい括弧列である。
  • )(, ()), (()()))(() は正しい括弧列ではない。

文字列 s が与えられるので、正しい括弧列かどうかを判定せよ。

入力

1行に文字列 s が与えられる。

条件

  • 1 \leq |s| \leq 2 \times {10}^{5}
  • s は ( または ) からなる。

出力

正しい括弧列のときは Yes を、そうでないときは No を出力すること。

解法

正しい括弧列となるには、 ) が存在したときに、その左側に対応する ( が存在することが必要です。

ここで、文字列 s を1文字目から順に見ていったときに、「 ( が現れたらスコアを1増やし、) が現れたらスコアを1減らす」ということを考えます。 （ただし、初期状態としてスコアは0であるとします。）

このとき、スコアが0の状態で ) が現れたとすると、その左側には対応する ( が存在しないということになります。 すなわち、スコアの経過を追っていったときに、スコアが負の値になることがあれば、それは正しい括弧列とは言えません。

また、文字列 s の最終スコアは、「対応する ) が存在せずに、余ってしまった ( の数」ということになります。

従って、最終スコアが0でないときについては、 ( が余ってしまっているという状態になるので、これも正しい括弧列とはなりません。

以上から、

  • スコアが負の値になることがない
  • 最終スコアが0である

の2つの条件を共に満たすことが、正しい括弧列となるための条件であると言えます。

文字列 s の各文字を左から順に見ていくため、これは O(|s|) の計算量で解くことができます。

ソースコード

main() 関数の中に、直接答えを出力する部分を実装しました。

int main() {
  string s;
  cin >> s;

  int score = 0; // 上記の「スコア」を表す
  for (int i = 0; i < s.length(); i++) {
    if (s[i] == '(') {
      score++; // 見ている文字が ( ならば、スコアを1増やす
    } else {
      score--; // 見ている文字が ) ならば、スコアを1減らす
    }

    if (score < 0) {
      No(); // スコアが負ならば No を出力して終了する
      return 0;
    }
  }

  if (score != 0) {
    No(); // 最終スコアが 0 でないならば No を出力する
  } else {
    Yes(); // 最終スコアが 0 ならば Yes を出力する
  }

  return 0;
}