[LeetCode] 1249. Minimum Remove to Make Valid Parentheses (Daily Question)

문제

---

Given a string s of '(' , ')' and lowercase English characters.

Your task is to remove the minimum number of parentheses ( '(' or ')', in any positions ) so that the resulting parentheses string is valid and return any valid string.

Formally, a parentheses string is valid if and only if:
    - It is the empty string, contains only lowercase characters, or
    - It can be written as AB (A concatenated with B), where A and B are valid strings, or
    - It can be written as (A), where A is a valid string.

 

문자열 s가 주어졌을 때 괄호 짝이 맞게 만들어야 하는 문제이다.

예를 들면, "lee(t(c)o)de)" 가 주어졌을 때 ")"하나가 남기 때문에 이를 없애고 반환하면 된다.

---

 

풀이

---

아이디어

문자열을 앞에서부터 살펴보며 열린괄호보다 닫힌괄호가 많아지는 순간에 닫힌괄호를 제거하고,

문자열을 뒤에서부터 살펴보며 닫힌괄호보다 열린괄호가 많아지는 순간에 닫힌괄호를 제거한다.

 

코드

class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:
        # pop 처리를 위해 s를 리스트로 변환
        s = list(s)
        cnt = 0
        i = 0
        while i < len(s):
            if s[i] == '(':
                cnt += 1
            elif s[i] == ')':
                if cnt > 0:
                    cnt -= 1
                # 열린 괄호보다 닫힌 괄호가 많아진 경우 pop 처리
                else:
                    s.pop(i)
                    i -= 1
            i += 1
            
        # s를 반대로 돌려 열린 괄호가 닫힌 괄호보다 많아진 경우 체크
        s = s[::-1]
        cnt = 0
        i = 0
        while i < len(s):
            if s[i] == ')':
                cnt += 1
            elif s[i] == '(':
                if cnt > 0:
                    cnt -= 1
                else:
                    s.pop(i)
                    i -= 1
            i += 1
            
        # s를 다시 문자열로 변환
        s = ''.join(s)[::-1]
        return s

 

---

 

후기

---

난이도

아이디어만 떠올리면 구현은 어렵지 않은 문제인 듯 하다.

 

하지만, 이런 풀이로는 빠른 속도를 내지 못했다.

만약 시간 조건이 빠듯해진다면, 다른 풀이를 생각해내는 것이 쉽지는 않을 것 같다.

 

다른 풀이

코드가 많이 지저분해서 s를 리스트로 바꿔 불필요한 부분을 삭제하는 것이 아닌,

새로운 문자열에 추가시키는 방법을 해봤으나...

 

Runtime이 6배정도 느려졌다. 

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

        for brackets in (("(", ")"), (")", "(")):
            s_temp = ""
            cnt = 0
            for c in s:
                if c == brackets[0]: 
                    cnt += 1
                elif c == brackets[1]:
                    if cnt > 0:
                        cnt -= 1
                    else: continue
                s_temp = c + s_temp

            s = s_temp
        
        return s