No.22 括弧の対応｜yukicoder｜stack - C++競プロ学習日記(仮)

括弧の対応、括弧列の問題は典型的な問題らしく、stack で解くと良いと教えて頂きました。

#include <bits/stdc++.h>
#define REP(i,n) for(int i=0; i<(n); i++)
using namespace std;
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
//開き側の位置も閉じ側の位置も分かっている(重要)
int main()
{
    int N, K;
    string S;
    cin >> N >> K >> S;
    
    stack<int> st;
    int res{};
    REP( i, (int)S.size() )
    {
        if( S[i] == '(' )
        {
            st.push( i + 1 );
            continue;
        }
        //括弧が ) の時 -> K番目が来たらstackのtopを保存する
        if( i + 1 == K )
        {
            res = st.top();
            break;
        }
        //括弧が ( の時 -> K番目がstackのtopに来たら閉じ括弧の位置を保存する
        if( st.top() == K )
        {
            res = i + 1;
            break;
        }
        st.pop();
    }
    cout << res << endl;
    return 0;
}

2回目の提出コード↑
1回目の提出でK番目の括弧の向きによって、括弧を反転させる...などという周りくどいコードを書いたのですが...そんな必要は全くなかったので書き直しました。
stackのtop()にある括弧の位置が分れば、閉じ括弧の位置も取得出来るので、括弧の向きに囚われがちなんですが、括弧の向きは重要ではない事が解りました。

#include <bits/stdc++.h>
#define REP(i,n) for(int i=0; i<(n); i++)
using namespace std;
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
//pairで対応する括弧のindexを保持していくversion
int main()
{
    int N, K;
    string S;
    cin >> N >> K >> S;
    
    vector<pair<int, int>> P;
    stack<int> st;
    
    REP( i, (int)S.size() )
    {
        if( S[i] == '(' )
        {
            st.push( i );
            continue;
        }
        //Lに'('のindex, Rに')'のindexを入れる
        int L = st.top() + 1;
        int R = i + 1;
        P.emplace_back( L, R  );
        
        st.pop();
    }
    for( auto &x : P )
    {
        if( x.first == K )
        {
            cout << x.second << endl;
            break;
        }
        if( x.second == K )
        {
            cout << x.first << endl;
            break;
        }
    }
    return 0;
}

3回目の提出↑
実はstackで解けると知る前、vector<pair<char, int>>で括弧とindexを保持していく解法でコード書いていたんですが...上手く行かず。
でもvectorでも書いてみたかったので、プロのコードを参考に書いてみました。
私はpairに括弧とindexを入れましたが、括弧は2種類しかないので、わざわざpairで持つ意味がないっぽかったです...。
その代わりに、leftとrightに分けて括弧と閉じ括弧のindexをpairで持ちました。
括弧が対応しているイメージで解けるのは良いかも...(？)

#include <bits/stdc++.h>
#define REP(i,n) for(int i=0; i<(n); i++)
using namespace std;
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
int main()
{
    int N, K;
    string S;
    cin >> N >> K >> S;
    
    stack<int> st;
    vector<int> res( N );
    REP( i, N )
    {
        if( S[i] == '(' )
        {
            st.push( i );
            continue;
        }
        int tmp = st.top();
        st.pop();
        res[i] = tmp;//left'(' のindex
        res[tmp] = i;//right')'のindex
    }
    cout << res[ K - 1 ] + 1 << endl;
    return 0;
}

↑最後、別解(プロのコード参照)
pairで左右の位置を保持すると、添字と左右の括弧の位置の3つの値を持ってしまう事になり、少し無駄があるという事で、pairでなく、vector<int>にして値を保持する書き方も。
コードがもっと簡潔になりました。

「括弧の対応を求める問題」はスタックを使うとうまく解けることが知られています

【初心者的スローガン】括弧列はstackで解く！*1
今回はこれを覚えました(おわり)

*1:必ずしもそうではないです