1249. Minimum Remove to Make Valid Parentheses (String, Stack)

링크 - https://leetcode.com/problems/minimum-remove-to-make-valid-parentheses/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Medium

Intuition

1) Using a Stack and String Builder

우리는 먼저 괄호에 대한 스택을 유지하면서 글자들을 탐색해야 한다. 

1. ans = "", opening_idx = [], idx_to_subs = 0으로 초기화한다.

2. 글자가 나오면 ans에 붙인다.

3. "("가 나오면 opening_idx에 현재 i값을 넣고 ans에 붙인다.

4. ")"가 나오면 opening_idx살펴본다. 만약 있으면 pop한뒤에 ans에 붙인다. 만약 아니라면 삭제해야하기 때문에 idx_to_subs값을 1 증가시킨다.

5. 다 끝나고 opening_idx가 남아있는지 확인한다. 있으면 pop을 해주면서 그 값에 idx_to_subs을 뺀 idx의 글자를 제거한다

class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:
        ans = ""
        opening_idx = []
        idx_to_subs = 0
        for i, c in enumerate(s):
            if c == "(":
                opening_idx.append(i)
                ans += c
            elif c == ")":
                if opening_idx:
                    opening_idx.pop()
                    ans += c
                else:
                    idx_to_subs += 1
            else:
                ans += c

        while opening_idx:
            idx = opening_idx.pop() - idx_to_subs
            ans = ans[:idx] + ans[idx+1:]

        return ans

Time Complexity: O(n) 처음에 s 돌면서 O(n), 나중에 opening_idx돌면서 O(n)

Space Complexity: O(n) ans와 opening_idx에 값을 저장하기 때문에 O(n)소모