921. Minimum Add to Make Parentheses Valid

leetcode.com/problems/minimum-add-to-make-parentheses-valid/

Minimum Add to Make Parentheses Valid - LeetCode

())(() 와 같이 parentheses가 주어졌을 때,

valid하게 만들기 위해서 몇 개를 추가해야 하는가?

구하는 문제, medium 으로 되어 있지만 easy 수준으로 정말 간단하다.

 

32ms

class Solution:
    def minAddToMakeValid(self, S: str) -> int:
        stack = []
        for c in S:
            if not stack:
                stack.append(c)
                continue
            if stack[-1] == '(' and c == ')':
                stack.pop()
            else:
                stack.append(c)
            
        return len(stack)            
            

 

20ms

와... ( 를 +, ) 를 -로 해석해서 더 빠르게 푼 방법

class Solution:
    def minAddToMakeValid(self, S: str) -> int:
        add = 0
        ex = 0
        for s in S:
            if s == "(":
                add += 1
            elif s == ")" and add <= 0:
                ex += 1
                add = 0
            else:
                add -= 1
        return add+ex