問題の説明

新しい開発者としてココアに入った「康」は、先輩の開発者から仕事の任務を受け、他の開発者が書いたソースコードを分析し、問題を発見し、修正するように要求された.ソースコードをコンパイルしてログを表示すると、ほとんどのソースコードのカッコがペアではない形式で記述されているため、エラーが発生します.
変更するソースファイルが多すぎるため、conはソースコードからカッコをすべて抽出し、カッコ文字列を正しい順序で表示するプログラムを開発することを検討しています.

用語定義

文字列が「(」と「)」のみで構成され、「(」の数と「)」の数が同じである場合は、バランスカッコ文字列と呼ばれます.
「(」と「)」のカッコが一致している場合は、正しいカッコ文字列と呼ばれます.
たとえば、文字列「()」(「」など)は「カッコ文字列のバランス」ですが、「有効カッコ文字列」ではありません.
逆に、文字列(()()などは「バランスのとれたカッコ文字列」であり、「正しいカッコ文字列」でもあります.
「(」と「)」のみからなる文字列wが「バランスの取れた括弧文字列」である場合、以下の手順で「正しい括弧文字列」に変換できます.

1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다. 
2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다. 
3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다. 
  3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다. 
4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다. 
  4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다. 
  4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다. 
  4-3. ')'를 다시 붙입니다. 
  4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다. 
  4-5. 생성된 문자열을 반환합니다.

パラメータとして「カッコ文字列のバランス」pを指定した場合、解法関数を完了し、指定したアルゴリズムを実行して「正しいカッコ文字列」に変換した結果を返します.

パラメータの説明

pは、2または1000より長い偶数の「(」および「)」のみからなる文字列です.

文字列pを構成する「(」および「)」の数は常に同じである.

pがすでに「正しいカッコ文字列」である場合、戻ることができます.

I/O例

p			result
"(()())()"	"(()())()"
")("		"()"
"()))((()"	"()(())()"

I/O例説明

I/O例#1
すでに「有効な括弧文字列」です.
I/O例#2
2つの文字列

をu、vに区切ります.
- u = ")("
- v = ""

uは「有効な括弧文字列」ではないため、次のように新しい文字列を作成します.
-vに対してステップ1からの再帰操作を実行すると、空の文字列が返されます.
-uの前後の文字を削除し、残りの文字の括弧の方向を反転すると「」になります.
-したがって、生成された文字列は「(+)」「+」「+」「+」であり、最終的に「()」に変換されます.

I/O例#3
2つの文字列

をu、vに区切ります.
- u = "()"
- v = "))((()"

文字列uは「正しい括弧文字列」であるため、それを保持し、vに対して再帰操作を実行する.

は、2つの文字列u、vを分離する.
- u = "))(("
- v = "()"

uは「有効な括弧文字列」ではないため、次のように新しい文字列を作成します.
-vに対して1ステップ目からの再帰操作が実行された場合は「()」を返します.
-uの前後の文字を削除し、残りの文字の括弧の方向を反転すると「()」になります.
-したがって、生成された文字列は「(」+「()」+「()」であり、最終的には「()()」を返します.

返された文字列が、最初に保持されていた文字列

に接続されると、"()"()+"()"()="()()()()になります.

方法

この問題は実施問題で,与えられた条件に従って再帰関数で書く最初は問題が理解できず、少し時間がかかりましたが、一歩一歩関数で実現して解決することができます.
次の関数を記述して解きました
cutting関数は、条件に従って

文字列を切り取るためのインデックスを返す.

カウント関数で、バランスカッコ文字列であるかどうかを確認する

関数

を検査し、括弧が正しいかどうかを検査する
逆関数

カッコ文字列のカッコ方向を反転

かっこ文字列を最終文字列として返すChange関数

これらの関数を適切に用いて問題を解決した.
sをパラメータとして宣言し、

文字列をトリミングするインデックスのcut関数を返します.
->「(」と「)」のカウント変数cnt 1、cnt 2は0です.
->sの長さが繰り返されるiのfor文.
-->s[i]が「(」の場合、cnt 1が増加します.
-->その他の場合はcnt 2を増やします.
-->cnt 1とcnt 2が同じ場合はiを返します.
->s의 길이-1に戻ります.

は、sをパラメータとして使用して、バランスカッコ文字列のカウント関数であるかどうかを決定することを宣言する.
->「(」と「)」のカウント変数cnt 1、cnt 2は0です.
->sの長さが繰り返されるiのfor文.
-->s[i]が「(」の場合、cnt 1が増加します.
-->その他の場合はcnt 2を増やします.
->cnt 1とcnt 2が同じ場合はTrueを返します.
->そうでなければfalseを返します.

は、sをパラメータとしてカッコ文字列が正しいかどうかを確認するチェック関数を宣言します.
->スタックとして使用するリストスタックを宣言します.
->sの長さが繰り返されるiのfor文.
-->s[i]が「(」)、
----->スタックにs[i]を入れます.
-->その他、
----->スタックが空の場合、
------>falseに戻ります.
----->スタックpop().
->Trueに戻ります.

パラメータとして

カッコを反転する逆関数sを宣言します.
->sをリストに変換します.
->sの長さが繰り返されるiのfor文.
-->s[i]が「(」)、
-->s[i]が「」に更新されました.
-->その他、
-->s[i]が「(」に更新されました.
->sは文字列を返します.

は、正しいカッコ文字列を返す関数変更sをパラメータとして宣言する.
->sが空の文字列の場合、空の文字列が返されます.cutting(s)の戻り値を変数idxに格納し、切り取り>sのインデックスを保存します.
->2つの文字列u,vをそれぞれs[:idx+1],s[idx+1:]と表す.
->checking(u)が真の場合、
-->u+change(v)に戻ります.
->checking(u)がfalseの場合、
-->一時変数tmpを'('+change(v)+')'+opposite(u[1:-1])と宣言します.
-->tmpを返します.

の正解を保存する変数の正解をchange(p)に選択します.

の答えを返します.

solution.py

def solution(p):
    def cutting(s):
        cnt1, cnt2=0, 0
        for i in range(len(s)):
            if s[i]=='(':
                cnt1+=1
            else:
                cnt2+=1
            if cnt1==cnt2:
                return i
        return len(s)-1
    def counting(s):
        cnt1, cnt2=0, 0
        for i in range(len(s)):
            if s[i]=='(':
                cnt1+=1
            else:
                cnt2+=1
        if cnt1==cnt2:
            return True
        else:
            return False
    def checking(s):
        stack=[]
        for i in range(len(s)):
            if s[i]=='(':
                stack.append(s[i])
            else:
                if not stack:
                    return False
                stack.pop()
        return True
    def opposite(s):
        s=list(s)
        for i in range(len(s)):
            if s[i]=='(':
                s[i]=')'
            else:
                s[i]='('
        return ''.join(s)
    def change(s):
        if not s:
            return ''
        idx=cutting(s)
        u, v=s[:idx+1], s[idx+1:]
        if checking(u):
            return u+change(v)
        if not checking(u):
            tmp='('+change(v)+')'+opposite(u[1:-1])
            return tmp
    answer = change(p)
    return answer