ABC064 D - Insertion

atcoder.jp

サクっと解けたものの、自分の読解力がなすぎるのか、 解説の言ってることが全く分からず・・・まさか嘘回答？

方針としてはこう

1. まず正しい括弧列は消えるイメージとする（ぷよぷよ的な）
2. 与えられたSで消えるものは全部消しきるまで、走査を繰り返す。文字数短いので
3. 消えるものが消え切った後の状態は、もう消えうるカッコがない。すなわち、以下の3パターンの組み合わせからしか成立しない
   1. 左から始まり、右まで続くかもしれない)))...
   2. 右から始まり、左まで続くかもしれない(((...
   3. これらの中間に一度だけありうる)(
4. よって、以下をやればOK
   1. 左から走査して、)の数だけ(を答えの左にくっつける
   2. 右から走査して（これが苦手なので、反転した文字列を左から走査している）、(の数だけ)を答えの右にくっつける

・・・これで通ったんだけど、解説が理解できないだけに、嘘回答じゃないか若干不安。いや、合ってるよな・・・

def resolve():
  N=int(input())
  S=input()
 
  Temp=S
  while True:
    Temp=Temp.replace("()","")
    if not "()" in Temp:
      break
 
  ans=S
 
  for t in Temp:
    if t==")":
      ans="("+ans
    else:
      break
 
  for t in Temp[::-1]:
    if t=="(":
      ans=ans+")"
    else:
      break
    
  print(ans)