1249. Minimum Remove to Make Valid Parentheses

문제링크

문제 이해

괄호의 짝을 찾아 맞추는 문제다.

Example 1:

Input: s = "lee(t(c)o)de)"
Output: "lee(t(c)o)de"
Explanation: "lee(t(co)de)" , "lee(t(c)ode)" would also be accepted.

상기 문제에서 볼수 있듯이 여러가지 답이 나올 수 있다고 하여, 여러가지 경우의수가 생길 수 있기에 recursive 문제로 생각했다.
하지만 return str을 해야한다면 재귀함수로 해결하기에 뭔가 애매했다.
뿐만 아니라 현재까지 모든 문제는 하나의 함수로 해결이 가능했는데, 부가적인 함수를 만든다는 것도 무언가 마음에 걸렸다.
또한 길이가 $10^5$ 이나 되는 입력 에 대해 여러 경우의수를 따지는 문제에서 재귀를 쓸 수는 없다고 생각했다.

반복문으로 해결하기

처음에 괄호의 짝을 맞춰야한다고는 생각했지만, 이게 괄호 좌우의 갯수가 같아야한다는 점을 활용하지 못 했다.
여러 가지 정답이 가능한만큼 순서는 따지지 않고 어떻게든 좌우짝만 맞으면 된다.

좌->우 방향으로만 생각한다면 경우의수가 많아지기에 if-else 가 복잡해진다.
이때 좌->우 한번 그리고 우->좌 한번씩 도는 것도 방법이다.

Solution

Trial 1

힌트롤 보고 좌로한번 우로한번 풀어보았는데, (())((을 해결하지 못했다. 좌우 갯수가 안맞아서 무지성으로 왼쪽부터 지웠더니 ))(( 라는 결과가 나와서 틀렸다.

class Solution:
    def minRemoveToMakeValid(self, stext: str) -> str:

        results = []

        dcount = 0
        left, right = 0,0
        for s in stext:
            if s ==')':
                if left == 0:
                    dcount += 1
                else:
                    right +=1
                    results += s
            else:
                results += s
                if s =='(':
                    left +=1
        
        # print(left, right)
        # print(results)

        if left<right:
            results = results[::-1]
            while left <right:        
                results.remove(')')
                right -=1
                dcount += 1
            results = results[::-1]


        # print(left, right)
        # print(results)
            

        while left > right:
            results.remove('(')
            left -=1
            dcount += 1

        # print(left, right)
        # print(results)

        return ''.join(results)

Trial 2

좌로 한번 우로 한번에서 벗어나지 못하여 함수를 하나 더 만들어서 해결했다.

class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:

        tmp = self.find(s, '(', ')')
        # print(tmp)
        tmp = tmp[::-1]        
        tmp = self.find(tmp, ')','(')
        tmp =tmp[::-1]
        # print(tmp)
        
        return tmp
        


    def find(self,stext , left_s, right_s):
        results = ''
        left, right =0,0
        
        for s in stext:
            if s == right_s:
                if left  >right:
                    results += s
                    right += 1
            
            else:
                if s == left_s:
                    left += 1
                
                results += s
                
        
        return results

참고

내가 짠 코드가 너무 지저분하여 다른사람걸 확인했다.

여기서 배울수 있는점은 나처럼 따로 str results를 만드는 대신 기존 str을 인덱스로접근하여 "" 빈칸으로만들고 이어붙이는 방법도 있다는 것이다.
이렇게되면 따로 삭제하거나 추가할 필요없이 제거해야할 대상만 공란으로 변경해주면 아주 간단하게 해결할 수 있다.

class Solution(object):
    def minRemoveToMakeValid(self, s):
        s = list(s)
        stack = []
        for i in range(len(s)):
            if s[i] == "(":
                stack.append(i)
            elif s[i] == ")":
                if len(stack):
                    stack.pop()
                else:
                    s[i] = ""
        for i in stack:
            s[i] = ""
        return "".join(s)