括弧の対応 (2) [yukicoder No.592] - はまやんはまやんはまやん

解法

「")"が出てきた場合に直前の対応が決まってない"("と対応する」ことを知らないと解けない。
そのため、先頭から順に括弧列を見ていくが、")"を発見したら、対応が決まってない直前の"("の場所を効率的に探していけばいい。
　
そのためにデータ構造であるスタックを使う。
これはFILO(First In Last Out)のデータ構造で、最後に入れたものが最初に取り出される。
　
これを使うと、先頭から順に括弧列を見ていくが、
"("ならばスタックに今の座標を入れる
")"ならばスタックから1つ取り出し（これが最後に入れてある対応が決まってない"("となる）、対応関係を確定する。
確定したら、それを答えとしてans配列に入れておき、最後に答える。

int N; string S;
int ans[201010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> S;

    stack<int> s;
    rep(i, 0, N) {
        if (S[i] == '(') s.push(i);
        else {
            int j = s.top(); s.pop();

            ans[i] = j;
            ans[j] = i;
        }
    }

    rep(i, 0, N) printf("%d\n", ans[i] + 1);
}