https://yukicoder.me/problems/no/592
解法
https://yukicoder.me/submissions/215754
「")"が出てきた場合に直前の対応が決まってない"("と対応する」ことを知らないと解けない。
そのため、先頭から順に括弧列を見ていくが、")"を発見したら、対応が決まってない直前の"("の場所を効率的に探していけばいい。
そのためにデータ構造であるスタックを使う。
これは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); }