ABC064 D – Insertion

はじめに

競プロの精進のために学びがあった問題についてまとめています。
目標は AtCoder 水色！

今のレートは茶色です。

問題

ABC064 D - Insertionを解きました。

( と ) で構成される N 文字の文字列 S が与えられる。
S にいくつかの ( または ) を挿入することで正しい括弧列を作りたい。

難易度は緑色。

考察

正しいかっこ列とは、( と ) が過不足なく閉じているものである。

つまり、 ( の右には同数の ) があり ) の左側には同数の ( が存在すると言い換えられる。

ここで、すべての文字列を精査した後、足りないものを足していけばよい。

辞書順については、 ( は左端、 ) は右端に貪欲的に追加していけばOK。

コード

N = int(input())
S = input()

left = 0
right = 0

for s in S:
    if s == ')':
        if left > 0:
            left -= 1
        else:
            right += 1

    if s == '(':
        left += 1

print('(' * right, end="")

left = 0
right = 0
for s in S[::-1]:
    if s == '(':
        if right > 0:
            right -= 1
        else:
            left += 1

    if s == ')':
        right += 1

print(S + ')' * left)

まとめ

かっこのカウントを一度にできなかったので、両サイドからそれぞれ実装したのですが、どうすればもっとシンプルにかけるんだろうか。

あと、ループを2回にしたせいでカウンタのリセットの考慮漏れをやらかしたので3回ペナりました。