[99클럽 코테 스터디 36일차 TIL] 스택

✏️  오늘의 문제 : 921. Minimum Add to Make Parentheses Valid

 

📌 주안점

• 입력은 '(' 혹은 ')'이 보장되고, 괄호가 닫혔는지 확인하고 빠진 공간을 확인하는 문제이다
• stack 자료구조를 이용해서 '('의 입력에는 top + 1, ')'의 입력에는 top - 1을 해준다.
  • 만약 top <= 0 인 경우에 ')' 입력이 들어온다면, '('를 하나 추가해주어야 한다.
  • 문자열 끝까지 순회를 마친 후 top만큼 ')'를 추가해주어야 한다.

 

📌 해결방법

class Solution:
    def minAddToMakeValid(self, s: str) -> int:
        ans = 0
        top = 0
        for i in s:
            if i == "(":
                top += 1
            else:
                if top <= 0:
                    ans+=1
                else:
                    top -= 1
        return ans+top