LeetCode 1021. Remove Outermost Parentheses

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₁ + P₂ + ... + 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.

 

유효한 문자열이란:

• 예를 들어, "", "()", "(())()", and "(()(()))", 모두 다 유효한 괄호 문자열이다.

기본 괄호 문자열이란 "()"이다 (()())의 기본 괄호 문자열들은 "()()"이다.

유효한 괄호 문자열 입력값을 받았을 때 모든 기본 괄호 문자열들의 가장 바깥쪽 괄호를 제거하라.

 

Example 1:

Input: s = "(()())(())"

Output: "()()()"

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

(()())(())   ()()의 가장 바깥 괄호를 제거하고 (())의 가장 바깥 괄호를 제거하면 ()이 남는다 그래서 ()()()이다.

 

Example 2:

Input: s = "(()())(())(()(()))"

Output: "()()()()(())"

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

(()()) 가장 바깥 괄호 제거 시 => ()()

(()) 가장 바깥 괄호 제거 시 => ()

(()(())) 가장 바깥 괄호 => ()(())

결과: ()()()()(())

 

Example 3:

Input: s = "()()"

Output: ""

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

()는 기본 괄호 문자열이다, ()의 바깥 괄호는 없으므로 ""이고 그다음 ()의 바깥 괄호도 ""이다 그래서 결과는 ""이다.

 

Constraints:

• 1 <= s.length <= 105
• s[i] is either '(' or ')'.
• s is a valid parentheses string.

 

처음에 이 문제를 스택으로 풀려했지만 바깥 괄호는 무조건 삭제시켜서 (())이든 ((()))이든 간에 결괏값이 ()만 나왔다.

만약 괄호가 2개 이상이라면 가장 바깥 괄호 쌍만 삭제하면 되지만 그렇게 할 방법을 못 찾아 유튜브에 풀이를 찾아봤다.

 

실패 코드

class Solution {
    public String removeOuterParentheses(String s) {
        Stack<Character> stack = new Stack<Character>();
        StringBuilder sb = new StringBuilder();
        
        for (char character : s.toCharArray()) {
            if (!stack.isEmpty() && character == stack.peek()) {
                stack.pop();
                stack.push(character);
            } else {
                stack.push(character);
            }
        }
        
        while (!stack.isEmpty()) {
            sb.insert(0, stack.pop());
        }
        
        return sb.toString();
    }
}

입력이 (()())(())(()(()))일시,

실패 코드 반환 값: ()()()()()

정답 반환 값: ()()()()(())

 

 

성공 코드 1

class Solution {
    public String removeOuterParentheses(String s) {
        Stack<Character> stack = new Stack<Character>();
        List<Integer> list = new ArrayList<Integer>();
        StringBuilder sb = new StringBuilder();
        
        for (int i = 0; i < s.length(); i++) {
            char currentChar = s.charAt(i);
            
            if (stack.isEmpty()) {
                list.add(i);
                stack.push(currentChar);
            } else if (stack.peek() == '(' && currentChar == ')' || stack.peek() == ')' && currentChar == '(') {
                stack.pop();
                if (stack.isEmpty()) {
                    list.add(i);
                }
            } else {
                stack.push(currentChar);
            }
        }
        
        for (int i = 0; i < list.size(); i += 2) {
            int startIdx = list.get(i);
            int endIdx = list.get(i + 1);
            
            sb.append(s.substring(startIdx + 1, endIdx));
        }
        
        return sb.toString();
    }
}

N = s 문자열 길이.

시간 복잡도: O(N)

공간 복잡도: O(N)

 

원리:

stack 변수는 바깥 괄호를 저장.

list 변수는 괄호 쌍들의 인덱스들을 저장함으로서 최종적으로 s.charAt(list 값) 문자들은 배제한 s값을 sb 변수 문자열에 할당.

 

예시: ( ( ) ( ) ) ( ( ) )

 

( ( ) ( ) ) ( ( ) )

i = 0

현재 문자 = '('

stack = '('                  스택이 비므로 현재 문자 추가.

list = [0]                    현재 문자 스택에 넣기 전 스택은 비므로 현재 인덱스 추가.

 

( ( ) ( ) ) ( ( ) )

i = 1

현재 문자 = '('

stack = '(', '('             스택 상위 값 == 현재 문자, 현재 문자 추가.

list = [0]

 

( ( ) ( ) ) ( ( ) )

i = 2

현재 문자 = ')' 

stack = '('                  스택 상위 값과 현재 문자 정반대,  pop() 함수 실행.

list = [0]

 

( ( ) ( ) ) ( ( ) )

i = 3

현재 문자 = '('

stack = '(', '('              스택 상위 값 == 현재 문자, 현재 문자 추가.

list = [0]

 

( ( ) ( ) ) ( ( ) )

i = 4

현재 문자 = ')'

stack = '('                  스택 상위 값과 현재 문자 정반대,  pop() 함수 실행.

list = [0]

 

( ( ) ( ) ) ( ( ) )

i = 5

현재 문자 = ')'

stack = '('                  스택 상위 값과 현재 문자 정반대,  pop() 함수 실행.

list = [0, 5]                pop() 함수 실행 후 스택은 비므로 현재 인덱스 추가.

 

( ( ) ( ) ) ( ( ) )

i = 6

현재 문자 = '('

stack = '('                 스택이 비므로 현재 문자 추가.

list = [0, 5, 6]            현재 문자 스택에 넣기 전 스택은 비므로 현재 인덱스 추가.

 

( ( ) ( ) ) ( ( ) )

i = 7

현재 문자 = '('

stack = '(', '('            스택 상위 값 == 현재 문자, 현재 문자 추가.

list = [0, 5, 6]

 

( ( ) ( ) ) ( ( ) )

i = 8

현재 문자 = ')'

stack = '('                스택 상위 값과 현재 문자 정반대,  pop() 함수 실행.

list = [0, 5, 6]

 

( ( ) ( ) ) ( ( ) )

i = 9

현재 문자 = ')'

stack = '('                스택 상위 값과 현재 문자 정반대,  pop() 함수 실행.

list = [0, 5, 6, 9]        pop() 함수 실행 후 스택은 비므로 현재 인덱스 추가.

 

list에 요소들은 s의 기본 괄호 문자열들의 바깥 괄호 인덱스들이다.

list = [0, 5, 6, 9]

sb = ""

 

for문 순회 시

i = 0

list.get(i)의 값 0

list.get(i + 1)의 값 5

s.substring(0, 5)의 값 "()()"

sb.append("()()")

sb = "()()"

i += 2

 

i = 2

list.get(i)의 값 6

list.get(i + 1)의 값 9

s.substring(6, 9)의 값 "()"

sb.append("()")

sb = "()()()"

 

sb.toString() 함수로 sb를 문자열로 변환.

 

 

 

 

성공 코드 2

LeetCode 토론방에서 발견한 간결한 코드.

스택도 필요 없어서 메모리와 스피드면에서 빠르다 하지만 시간 복잡도와 공간 복잡도는 변함이 없다.

 

class Solution {
    public String removeOuterParentheses(String s) {
        StringBuilder sb = new StringBuilder();
        int bracketCount = 0;
        int bracketStartIdx = 0;
        
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                bracketCount++;
            } else if (s.charAt(i) == ')') {
                bracketCount--;
            }
            
            if (bracketCount == 0) {
                sb.append(s.substring(bracketStartIdx + 1, i));
                bracketStartIdx = i + 1;
            }
        }
        
        return sb.toString();
    }
}

N = s 문자열 길이.

시간 복잡도: O(N)

공간 복잡도: O(N)

 

bracketCount라는 변수로 여는 괄호와 닫는 괄호를 주시한다 (여는 괄호 발견 시 1 추가, 닫는 괄호 발견 시 1 빼기).

bracketStartIdx 변수는 바깥 괄호 인덱스를 추종한다.

 

만약 bracketCount 변수가 0이라면 바깥 괄호가 닫힌다는 것이다 그러면 성공코드 1과 동일하게 substring() 함수로 바깥 괄호만 배제한 s를 sb에 덧붙인다.

예를 들어, s가 (())일시, 마지막 for문에서 i =3, bracketCount가 0되고, substring(0 + 1, 3) 반환 값을 sb에 덧붙혀,

sb은 ()이 된다.