ABC307D - Mismatched Parentheses

考え方

アライグマ「D問題はスタックなのだ！　「前から見て')'が来たら、直前の'('からここまでを削除」とすればいいのだ。今までに'('が何個あるかを覚えておいて、1個以上のときだけ'('を探せば全体でO(N)になるのだ！」

— 競技プログラミングをするフレンズ (@kyopro_friends) June 24, 2023

回答例

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

stack = []
cnt = 0
for i in range(N):
    s = S[i]
    if s == '(':
        cnt += 1

    if cnt > 0 and s == ')':
        while True:
            cur = stack.pop()
            if cur == '(':
                break
        cnt -= 1
        continue

    stack.append(s)

print(''.join(stack))