921. Minimum Add to Make Parentheses Valid

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

 

Difficulty : Medium

 

Status : Solved

 

Time : 00:00:32

 

---

 

문제 설명

 

괄호 문자열은 아래 조건을 만족할 때 유효하다고 한다.

 

* 문자열이 비었거나,

* A, B가 유효한 문자열일때 AB의 형태이거나

* A가 유효한 문자열일때 (A)의 형태일 때.

 

괄호 문자열 s가 주어진다. 한 번의 이동에서 문자열의 어떤 부분에 괄호를 하나씩 삽입할 수 있다.

* 예를 들어, s="()))"이라면 여는 괄호를 삽입해서 "(()))"로 만들거나 닫는 괄호를 삽입해서 "())))"를 만들 수 있다.

s를 유효하게 만드는 최소 이동을 구하여라.

---

 

풀이

 

...어제랑 똑같은 문제.

2024.10.09 - [PS/LeetCode] - 1963. Minimum Number of Swaps to Make the String Balanced

1963. Minimum Number of Swaps to Make the String Balanced

스택으로 풀이하면 된다.

 

풀이 코드

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