[코딩연습] Remove Outermost Parentheses 바깥 괄호 제거하기

LeetCode 문제 중 난이도 Easy인 Remove Outermost Parentheses이다. 문제 링크는 포스팅의 맨 마지막에 추가하였다. 언어는 Java를 사용했다.

  문제해석

유효한 괄호 문자열은 비어있는 (""), "(" + A + ")", 또는 A + B이다. 여기서 A와 B는 유효한 괄호 문자열이며, +는 문자열의 연결을 나타낸다. 예를 들어 "", "()", "(())()", "(()(()))"는 모두 유효한 괄호 문자열이다.

유효한 괄호 문자열 S가 비어 있지 않고, A와 B가 비어 있지 않은 유효한 괄호 문자열을 사용하여 S = A+B로 분할할 수 있는 방법이 없으면 원시적이라고 한다.

주어진 유효한 괄호 문자열 S의 원시분해를  S = P_1 + P_2 + ... + P_k라 하자. (P_i는 원시적인 유효한 괄호 문자열)

S의 원시 분해에서 가장 바깥쪽 괄호를 제거한 모든 원시 문자열을 반환해라.

가장 바깥쪽 괄호인지 체크하기 위해서 open이라는 변수를 사용한다. i번째 인덱스가 여는괄호이면 +1, 닫는괄호이면 -1을 해준다. open이 양수면 괄호가 열린상태이다.

open이 0일때의 여는괄호와 1일때의 닫는괄호가 가장 바깥쪽 괄호일 것이다. 가장 바깥쪽 괄호를 제거하기 위해서 open이 0일때 여는괄호와 open이 1일때 닫는괄호가 아닌 문자들만 sb에 덧붙인다.

class Solution {
    public String removeOuterParentheses(String S) {
        
        StringBuilder sb = new StringBuilder();
        int open = 0;
        
        for(int i = 0 ; i<S.length() ; i++){
            if(S.charAt(i) == '(' ){
                if(open != 0) sb.append(S.charAt(i));
                open++;
            }else{
                if(open != 1) sb.append(S.charAt(i));
                open--;
            }    
        }
        return sb.toString();
    }
}

이 풀이의 시간복잡도는 O(n)이고 공간복잡도도 O(n)이다.

문제출처 - https://leetcode.com/problems/remove-outermost-parentheses/