1249. Minimum Remove to Make Valid Parentheses

#String #Stack

 

괄호 '(', ')' 나 소문자로 이루어진 문자열 s 가 주어진다.

최소 개수의 괄호를 삭제한 유효 문자열을 반환하라.

 

일반적으로, 괄호 문자열은 다음의 경우에 유효하다.

• 빈 문자열이거나 소문자만 포함된 문자열
• 유효한 문자열 A,B 가 연결된 문자열
• 유효한 문자열 A로 이루어진 문자열 (A)

 

---

 

Trial 1 : Python3, 22/03/15

class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:
        s = list(s)     # 문자열을 리스트로 변환
        tmp = []        # 괄호 임시 저장할 리스트 선언
        for i, char in enumerate(s):	# enumerate() 메소드는 인덱스와 요소 함께 반환
            if char == '(':
                tmp.append(i)   # 요소가 '(' 일 때 임시리스트에 저장
            elif char == ')':
                if tmp:         # 리스트가 비어있으면 False, 아니면 True 반환
                    tmp.pop()   # 요소가 ')' 이고 임시리스트가 비어있지 않을 때
                else:
                    s[i] = ''   # 요소가 ')' 이고 임시리스트가 비어있을 때
        while tmp:
            s[tmp.pop()] = ''   # 임시리스트에 남은 '(' 처리
        return ''.join(s)

풀이

문제를 단순하게 정리해보면 문자열에 '(' (이하 앞괄호) 가 있으면 반드시 ')' (이하 뒷괄호) 가 나와야 하며 어느 한 짝이 모자라면 해당 괄호는 삭제해야 한다.

문자열의 문자를 하나씩 탐색하면서 앞괄호가 나오면 임시리스트에 해당하는 인덱스를 저장하고 이후에 뒷괄호가 나오면 임시리스트에서 가장 마지막 인덱스를 삭제한다.

만약 문자가 뒷괄호인데 임시리스트가 비어있으면(앞괄호가 나온 적이 없으면) 뒷괄호 문자를 지운다.

문자열 탐색이 끝나고 임시리스트를 탐색하면서 남아있는 앞괄호를 지운다.

인덱스를 사용하기 위해 주어진 문자열을 리스트로 변환해 사용하고 반환할 때는 join() 메소드를 이용해 문자열로 변환해서 반환한다.

 

* str.join(list) : str+list(str으로 변환)

* 조건문에서는 리스트가 비어있으면 False, 비어있지 않으면 True 를 반환한다.

 

 

리뷰

런타임 최대 98.15%, 메모리 최대 66.40% 까지의 결과를 얻었다.

파이썬의 기본 메소드와 성질을 이용해서 간단하게 문제를 해결하는 방법을 하나씩 얻어가고 있어서 기분이 좋다.