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

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]

1249. Minimum Remove to Make Valid Parentheses

Problem link

Problem Summary

Solution

Source Code