1249. Minimum Remove to Make Valid Parentheses

[zeikar]

Problem link

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

Problem Summary

올바른 괄호 문자열이 되도록 최소한의 문자를 제거하는 문제.

Solution

최소한을 제거해야 하므로 제거할 필요가 없는 애들은 놔둬야 한다.
즉, 올바른 괄호면 제거하지 않고 올바르지 않은 괄호만 골라서 지우면 된다.

간단한 카운터를 하나 두고 (가 나오면 ++, )가 나오면 --로 해서 올바른지 판단할 수 있다. 이렇게 하면 열지 않았는데 닫는 괄호를 제거해줄 수 있고 닫지 않고 열기만 하는 괄호는 뒤에서 부터 남은 카운트만큼 열린 괄호를 지워주면 된다.

Source Code

class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:
        temp = ""
        cnt = 0

        for ch in s:
            if ch == '(':
                cnt += 1
                temp += ch
            elif ch == ')':
                if cnt != 0:
                    temp += ch
                    cnt -= 1
            else:
                temp += ch

        ans = ""
        for ch in temp[::-1]:
            if ch == '(' and cnt > 0:
                cnt -= 1
            else:
                ans += ch

        return ans[::-1]