[99클럽] 36일차 TIL

https://leetcode.com/problems/minimum-add-to-make-parentheses-valid/submissions/1299761990/

 

오늘의 문제는 괄호 스택 문제입니다.

 

예전에 스택 관련해서 문제를 많이 풀어봐서 빠르게 풀게되었습니다.

 

먼저 (가 입력되면 stack에 채워줍니다. 그리고 )닫히는 괄호가 나오면 pop을 해줘서 stack에서 최근 것을 빼줍니다.

하지만 stack이 비어있을 때 )가 입력되는 경우도 있으니 이 때는 카운트를 해줍니다.

그리고 마지막으로 stack에 ( 입력이 쌓여있을 수 있으니 카운트 값에 마지막에 stack의 들어있는 개수만큼 더해주어 구현하였습니다.

 

class Solution:
    def minAddToMakeValid(self, s: str) -> int:
        stack = []
        cnt = 0
        for st in s:
            if st == "(":
                stack.append("(")
            elif st == ")" and len(stack) == 0:
                cnt += 1
            else:
                stack.pop()
        cnt += len(stack)

        return cnt