はじめに
競プロの精進のために学びがあった問題についてまとめています。
目標は 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回ペナりました。