Remove Outermost Parentheses (1021)

14 Apr 2020 in Algoirthm

leetcode 1021번 문제 (java)

문제 내용

A valid parentheses string is either empty (“”), “(“ + A + “)”, or A + B, where A and B are valid parentheses strings, and + represents string concatenation. For example, “”, “()”, “(())()”, and “(()(()))” are all valid parentheses strings. A valid parentheses string S is primitive if it is nonempty, and there does not exist a way to split it into S = A+B, with A and B nonempty valid parentheses strings. Given a valid parentheses string S, consider its primitive decomposition: S = P_1 + P_2 + … + P_k, where P_i are primitive valid parentheses strings. Return S after removing the outermost parentheses of every primitive string in the primitive decomposition of S.

=>

• Example

  Input: "(()())(())"
  Output: "()()()"
  Explanation: 
  The input string is "(()())(())", with primitive decomposition "(()())" + "(())".
  After removing outer parentheses of each part, this is "()()" + "()" = "()()()".
  

  -Example 2

  Input: "(()())(())(()(()))"
  Output: "()()()()(())"
  Explanation: 
  The input string is "(()())(())(()(()))", with primitive decomposition "(()())" + "(())" + "(()(()))".
  After removing outer parentheses of each part, this is "()()" + "()" + "()(())" = "()()()()(())".
  

• 범위

  S.length <= 10000
  S[i] is "(" or ")"
  S is a valid parentheses string
  

내가 찬 코드

class Solution {
    public String removeOuterParentheses(String S) {
        StringBuilder SB = new StringBuilder();
        int count = 0;
        int start = 0;
        for (int i = 0; i < S.length(); i++) {
          if (count == 0) {
            start = i;
          }
          if (S.charAt(i) == '(') {
            count++;
          } else {
            count--;
          }
          if (count == 0) {
            SB.append(S.substring(start + 1, i));
          }
        }

        return SB.toString();
    }
}

굳이 substring을 사용할 필요는 없었던것 같다.

더 빠른 실행 속도를 가진 코드

class Solution {
    public String removeOuterParentheses(String S) {
        int stack = 0;
        StringBuilder result = new StringBuilder();

        
        for(char c : S.toCharArray()){
            
            if(c == '('){
                stack ++;
                
                if(stack != 1 ){
                    result.append(c);
                }
                
            } else {
                stack--;
                if(stack != 0){
                    result.append(c);
                }
            }
            
        }

        return result.toString();
    }
}