[LeetCode] Remove Outermost Parentheses (1021번)

출처

1021. Remove Outermost Parentheses

문제

입력으로 들어온 각 valid parentheses의 가장 바깥쪽에 있는 괄호를 제거하는 간단한 문제이다. valid parentheses란 괄호의 짝이 모두 올바르게 구성된 것을 의미한다. 입력으로 항상 valid parentheses string이 들어온다는 전제 조건이 있기 때문에, 별도로 괄호를 검증하는 과정은 필요없다. 문자열 연산을 이용하면 더 간단하게 풀 수 있지만, stack 자료구조를 활용하여 풀어보았다.

풀이

class Solution:
    def removeOuterParentheses(self, s: str) -> str:
        stack = []
        count = 0
        outer = False
        flag = True
        
        for ch in s:
            if ch == '(':
                stack.append(ch)
                count += 1
                if count >= 1 and flag:
                    stack.pop()
                    outer = True
                    flag = False
            else:
                stack.append(ch)
                count -= 1
                if outer and count == 0:
                    stack.pop()
                    outer = False
                    flag = True
                    
        return "".join(map(str, stack))

먼저 괄호를 저장할 스택을 선언해준다. count 변수를 통해 ( 가 들어올 때 1을 증가시키고, ) 가 들어올 땐 1씩 감소시켜 하나의 온전한 valid parentheses가 모두 입력되었는지 확인한다.

ex) ( ( ) ( ) ) 가 입력으로 들어왔다고 가정했을 때, count 변수는 1, 2, 1, 2, 1, 0으로 순차적으로 변화한다. 즉, count 변수가 0이 되었을 때 하나의 valid parentheses에 대한 입력이 끝났음을 알 수 있다.

outer 변수는 초기에 ( 가 연속으로 2번 들어왔을 때 outermost parentheses가 존재한다는 것을 알려준다. outer가 true면 valid parentheses 내에 삭제할 괄호가 아직 남아있다는 의미이다. flag 변수는 outer 변수의 값에 대한 변경이 한 valid parentheses 내에서 1번만 수행되도록 하기 위해 선언하였다. ) 를 입력으로 받을 때 count 변수의 값을 1 감소시키고, count 변수가 0이고 outer가 true면 (삭제할 괄호가 남아있으면) stack에 pop연산을 수행하고 outer, flag 변수의 값을 변경한다.

시간 복잡도

$O(N)$

실행 결과