LeetCode [1190]: Reverse Substrings Between Each Pair of Parentheses

📌 LeetCode [1190]: Reverse Substrings Between Each Pair of Parentheses

🔗 문제 링크

---

문제 설명 📄

주어진 문자열 s에서 각 괄호 쌍 안에 있는 문자열을 뒤집은 결과를 반환하세요. 중첩된 괄호를 처리해야 하며, 모든 괄호는 유효합니다.

---

문제 해결 접근

1. 문자열을 순회하면서 괄호에 따라 처리를 나눕니다.
2. 괄호가 열리면(() 재귀적으로 내부를 처리합니다.
3. 괄호가 닫히면()) 현재까지 쌓인 문자열을 뒤집어 반환합니다.
4. 문자열의 끝까지 탐색 후 스택에 남은 모든 문자를 합쳐 반환합니다.

---

Solution 💻

class Solution:
    def reverseParentheses(self, s: str) -> str:
        index = 0
        def order():
            nonlocal index
            stack = []
            while index < len(s):
                if s[index] == "(":
                    index += 1
                    stack += order()
                elif s[index] == ")":
                    return list(reversed(stack))
                else:
                    stack.append(s[index])
                index += 1
                
            return stack

        return "".join(order())

---

시간 복잡도 분석 ⏲️

• 재귀 탐색: 문자열의 길이를 기준으로 각 문자를 한 번씩 탐색 → O(n).
• 문자열 뒤집기: 괄호 내부의 문자열 뒤집기 작업이 필요 → O(k) (여기서 k는 괄호 안에 포함된 최대 문자 수).
• 최종 시간 복잡도: O(n + k).

---

공간 복잡도 분석 🗄️

• 재귀 호출 스택: 괄호의 최대 중첩 깊이에 비례 → O(d) (여기서 d는 중첩된 괄호의 깊이).
• 스택 사용: 스택에 문자 저장 → O(n) (문자열 전체를 스택에 저장 가능).
• 최종 공간 복잡도: O(n + d).

---