Yukicoder022 括弧の対応

問題概要

長さ$N$の括弧列が与えられる。1-indexで$K$番目の括弧に対応する括弧の位置を求めよ。

$N\leqq10^4$、$1\leqq K\leqq N$

yukicoder022

解法

ある括弧に対応する括弧の位置はstackでわかるので、 $K$番目のものだけ色付けをして発見すればよい。

計算量:$O(N)$

ソース

    #include <bits/stdc++.h>
    using namespace std;
    
    using VS = vector<string>;    using LL = long long;
    #define SZ(a) int((a).size())
    #define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
    #define FORR(i, s, e) for (int(i) = (s); (i) > (e); (i)--)
    
    LL N;
    LL ans = 0LL;
    
    int main() {
        cin.tie(0);
        ios_base::sync_with_stdio(false);
    
        int  K; cin >> N >> K;
        string s; cin >> s;
    
        if (s[K - 1] == '(') {
            stack<int>st;
            FOR(i, 0, SZ(s)) {
                if (s[i] == '(') {
                    if (K - 1 == i)st.push(1);
                    else st.push(0);
                }
                else {
                    if (SZ(st)) {
                        int a = st.top(); st.pop();
                        if (a)ans = i + 1;
                    }
                }
            }
        }
        else {
            stack<int>st;
            FORR(i, SZ(s) - 1, 0 - 1) {
                if (s[i] == ')') {
                    if (K - 1 == i)st.push(1);
                    else st.push(0);
                }
                else {
                    if (SZ(st)) {
                        int a = st.top(); st.pop();
                        if (a)ans = i + 1;
                    }
                }
            }
        }
    
        cout << ans << "\n";
    
        return 0;
    }