[Leet Code] 1021. Remove Outermost Parentheses

문제 원본: https://leetcode.com/problems/remove-outermost-parentheses/

문제

유효한 괄호 문자열은 "", "(" + A + ")", A + B 이다. 여기서 A와 B는 유효한 괄호 문자열이고, +는 문자열 결합을 의미한다.

• 예시로 "", "()", "(())()", "(()(()))"은 모두 유효한 괄호 문자열이다.

유효한 괄호 문자열 s는 만약 비어있지 않다면 기본적인 요소이고(primitive), s = A + B (A, B는 비어있지 않은 유효한 괄호 문자열)로 나누는 방법은 없다.

유효한 괄호 문자열 s가 주어지면, 그것의 근본적인(primitive) 분해 방법은 s = P1 + P2 + ... + Pk가 있다. 이때 Pi는 유효한 괄호 문자열의 기본 요소(primitive)이다.

s의 근본적인(primitive) 분해에서의 모든 원시(primitive) 문자열의 가장 바깥쪽 괄호를 제거한 후 반환하라.

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 <= 10^5
• s[i]는 '(' 또는 ')'이다.
• s는 유효한 괄호 문자열이다.

접근 방법

이 문제의 핵심 부분은 “어떻게 제일 바깥쪽의 괄호인지를 판단할 것인가”라고 생각했다. 그래서 처음에는 괄호의 ‘(‘ 부분이 나올 때마다 isInner = true, ‘)’이 나오면 isInner = false으로 스위치하면서 isInner = 1일 때에만 문자열을 concat할 예정이었다. 그런데 그렇게 하면 (())로 출력해야 하는 부분은 제대로 출력이 되지 않을 게 뻔했다.

그래서 이번에는 ‘(‘이 나오면 depth++;, ‘(‘이 나오면 depth--;를 하게 했다. 여기서 depth 변수는 이게 몇 번 중첩된 괄호인지를 나타낸다. 즉, (())라면 가장 안쪽 괄호의 depth는 2가 될 것이다. 그래서 첫 번째 중첩(제일 바깥)을 제외하고 그 다음 중첩부터 문자열을 concat하면 될 것이다. 괄호가 (())()처럼 여러 개 있다 하더라도, 하나의 괄호 집합 (())이 끝나면 다시 depth = 0이 될 것이니, 그 다음 괄호 집합이 나와도 문제 없다.

풀이

Java

class Solution {
    public String removeOuterParentheses(String s) {
        StringBuilder inner = new StringBuilder();
        int depth = 0;
        
        for (char c : s.toCharArray()) {
            if (c == '(')
                depth++;
            if (depth > 1)
                inner.append(c);
            if (c == ')')
                depth--;
        }
        return inner.toString();
    }
}

• Runtime: 2ms
• Memory: 41.8MB

String vs StringBuilder vs StringBuffer

상위권 유저들을 보면 String 자료형을 썼을 때보다 StringBuilder를 썼을 때 더 좋은 성능을 보여줬다. 왜 String이 StringBuilder보다 느릴까?
알고보니 String은 불변의 속성을 가지기 때문에, 문자열의 내용이 달라지면 새로운 메모리 영역을 가리킨다. 그러면서 새로운 메모리 영역을 할당하고, 원래 메모리 영역은 Garbage로 남아있다가 Garbage collection에 의해 사라진다. 즉, 문자열을 수정하면 새로운 String 인스턴스를 생성한다.
반면에 StringBuilder는 가변적이기 때문에, 동일한 객체 내에서 문자열을 변경할 수 있다. 따라서 문자열의 추가, 수정, 삭제가 빈번하다면 StringBuilder를, 그렇지 않다면 String을 쓰는 게 적합하다고 한다.

번외로 StringBuilder와 같은 역할을 하는 StringBuffer도 있는데, 둘의 차이는 각각 동기화의 유무이다. StringBuffer는 동기화를 지원해서 멀티 스레드에서 안전하지만, StringBuilder는 동기화를 지원하지 않는다. 그러나 단일 스레드에서는 StringBuilder가 더 좋은 성능을 보인다.
그래서 StringBuffer를 사용할 수 있음에도 불구하고, StringBuilder를 사용하는 것이었다.

출처: https://ifuwanna.tistory.com/221

C#

public class Solution {
    public string RemoveOuterParentheses(string s) {
        String inner = "";
        int depth = 0;
        
        foreach (char c in s.ToCharArray()) {
            if (c == '(')
                depth++;
            if (depth > 1)
                inner += c;
            if (c == ')')
                depth--;
        }
        return inner;
    }
}

• Runtime: 143ms
• Memory: 36MB

Python

class Solution:
    def removeOuterParentheses(self, s: str) -> str:
        inner = ""
        depth = 0
        
        for c in s:
            if c == '(':
                depth += 1
            if depth > 1:
                inner += c
            if c == ')':
                depth -= 1
        return inner

• Runtime: 58ms
• Memory: 14MB