yukicoder No.22 括弧の対応

問題

問題のURLはこちらです。
No.22 括弧の対応 - yukicoder

考えたこと

まず、入力された各括弧の深さを表す配列をいもす法を使って格納しておきます。

いもす法に関しては、こちらの記事を参照してください。
satanic0258.hatenablog.com

そして、調べる番目の括弧が

• 「」なら、右方向へ
• 「」なら、左方向へ

番目の括弧と同じ深さの括弧を探していきます。
それで一番最初に見つかったものが、番目に対応する括弧となります。

コード(C++)

#86196 No.22 括弧の対応 - yukicoder

#include <iostream>
#include <vector>

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    char check;
    int N, K, ans;
    std::cin >> N >> K;
    std::vector<int> bracket(N+1, 0);
    for(int i=0; i<N; ++i){
        char input;
        std::cin >> input;
        if(i==K-1) check=input;
        switch(input){
            case '(': ++bracket[i]; break;
            case ')': --bracket[i+1]; break;
        }
    }
    for(int i=1; i<N+1; ++i){
        bracket[i] += bracket[i-1];
    }
    if(check=='('){
        ans=K+1;
        while(bracket[K-1]!=bracket[ans-1]) ++ans;
    }else{
        ans=K-1;
        while(bracket[K-1]!=bracket[ans-1]) --ans;
    }
    std::cout << ans << "\n";
            
    return 0;
}

コードの説明など

for(int i=0; i<N; ++i){
    char input;
    std::cin >> input;
    if(i==K-1) check=input;
    switch(input){
        case '(': ++bracket[i]; break;
        case ')': --bracket[i+1]; break;
    }
}
for(int i=1; i<N+1; ++i){
    bracket[i] += bracket[i-1];
}

この部分では、「いもす法」で各括弧の深さを配列bracketに入れています。

if(check=='('){
    ans=K+1;
    while(bracket[K-1]!=bracket[ans-1]) ++ans;
}else{
    ans=K-1;
    while(bracket[K-1]!=bracket[ans-1]) --ans;
}

この部分では、「考えたこと」でも述べたように番目の括弧に対応する括弧が何番目にあるかを調べています。

備考

この方法では、「各括弧の深さを求める（）」＋「番目と同じ深さの括弧を探す（）」という２つの処理を行っています。

しかし、他の方の解説を見ると「番目の深さを基準として一方向に移動しながら相対的な深さが0になるところを探す（）」や「初めから調べて開き括弧なら位置番号をstackに格納して、閉じ括弧ならstackの先頭要素を削除していき、どちらか一方がであったとき、もう一方を答とする（）」など、この解説とは別の解答もあります。

よって、この記事の方法が唯一の解だということはありません。

感想など

やはり他の方の回答には、いくらか効率的であったり簡単であるものがあると思います。

そのため、「なんとか自力でAC出来た！」という時も、他の方の回答を見てみることで新たな発見があったり、勉強になることもあるので、問題を解いたらそのままにすること無く復習をしていくこともスキル上達のために必要なことではないでしょうか。

…と、自分の解法と他の方の解説との違いを改めて認識させられた問題だと思いました。