[리트코드] 1190 - Reverse Substrings Between Each Pair of Parentheses

1190. Reverse Substrings Between Each Pair of Parentheses

Medium

---

You are given a string s that consists of lower case English letters and brackets.

Reverse the strings in each pair of matching parentheses, starting from the innermost one.

Your result should not contain any brackets.

 

Example 1:

Input: s = "(abcd)"
Output: "dcba"

Example 2:

Input: s = "(u(love)i)"
Output: "iloveu"
Explanation: The substring "love" is reversed first, then the whole string is reversed.

Example 3:

Input: s = "(ed(et(oc))el)"
Output: "leetcode"
Explanation: First, we reverse the substring "oc", then "etco", and finally, the whole string.

 

Constraints:

• 1 <= s.length <= 2000
• s only contains lower case English characters and parentheses.
• It is guaranteed that all parentheses are balanced.

분류

문자열, 스택, Bracket Sequences

---

문제 풀이

문제 분석

주어진 문자열 s는 소문자와 괄호 ( , ) 로만 구성되어 있습니다.
문제는 일치하는 괄호 쌍 사이의 부분 문자열을 뒤집으되, 가장 안쪽에 있는 괄호부터 순서대로 처리하라는 것입니다.
최종 결과에는 괄호가 포함되어서는 안 됩니다.

• 입력: 괄호가 균형을 이루는 문자열 s (길이 1 ~ 2000)
• 출력: 모든 괄호가 처리되어 제거되고, 지정된 규칙대로 뒤집힌 최종 문자열

---

접근 방법

이 문제는 스택(Stack) 자료구조를 활용하여 해결합니다.

이유:

1. 괄호 문제는 '가장 안쪽(Last In)'부터 처리해야 하므로 후입선출(LIFO) 특성을 가진 스택이 자연스럽게 맞습니다.
2. 여는 괄호 ( 를 만나면 스택에 넣고, 닫는 괄호 ) 를 만나면 바로 직전의 여는 괄호 ( 까지의 문자열을 꺼내서 뒤집은 뒤 다시 스택에 넣는 과정을 반복하면 됩니다.
3. 문자열 길이가 최대 2000이므로, 스택을 이용한 선형 탐색(O(N))으로 충분히 시간 내에 해결 가능합니다.

---

구현 설명

1. 스택 초기화 및 문자 순회

stack = []
for x in s:

빈 스택을 생성하고, 입력 문자열 s의 각 문자 x를 순차적으로 탐색합니다.

2. 닫는 괄호 ) 를 만났을 때: 내부 문자열 추출 및 뒤집기

if x == ")":
    arr = []
    while stack and stack[-1] != "(":
        arr.append(stack.pop())
    
    stack.pop()  # 여는 괄호 '(' 제거
    stack += arr # 뒤집힌 문자열(arr)을 스택에 다시 합침

• 현재 문자가 ) 라면, 스택의 top부터 여는 괄호 ( 가 나올 때까지 문자를 꺼내 arr 리스트에 담습니다.
• pop()을 순서대로 수행하므로 arr에는 이미 뒤집힌 순서로 문자가 저장됩니다.
• 스택에 남아있는 여는 괄호 ( 를 pop()으로 제거합니다.
• 뒤집힌 문자열 리스트 arr을 스택 뒤에 이어 붙입니다(stack += arr).

3. 그 외 문자(소문자, 여는 괄호) 처리

else:
    stack.append(x)

닫는 괄호가 아니라면(소문자 또는 (), 단순히 스택에 푸시합니다.

4. 최종 결과 반환

return "".join(stack)

모든 문자를 처리한 후 스택에 남은 문자들을 합쳐 문자열로 반환합니다. 이 시점에는 모든 괄호가 제거되고 올바르게 뒤집힌 상태입니다.

---

⏱복잡도 분석

• 시간 복잡도: O(N)

  • N은 문자열 s의 길이입니다.
  • 각 문자는 최대 두 번 스택에 들어갔다 나옵니다(한 번 push, 한 번 pop). while 루프 내부에서 문자를 꺼내는 연산도 전체 문자 수를 합치면 O(N)입니다. 리스트 합치기(+=) 역시 전체 요소 수만큼 수행되므로 총 O(N)입니다.

• 공간 복잡도: O(N)

  • 스택에 최대 문자열 길이만큼의 문자가 저장될 수 있습니다. 임시 리스트 arr 또한 최대 O(N) 크기를 가집니다.

---

핵심 포인트

1. 스택의 LIFO 특성 활용: 괄호 문제에서 '가장 안쪽부터 처리'라는 요구사항은 스택의 후입선출 구조와 완벽하게 일치합니다.
2. 자연스러운 뒤집기 효과: 스택에서 pop()하여 임시 리스트에 append()하는 과정 자체가 문자열을 뒤집는 연산이 됩니다. 별도의 reverse() 함수가 필요 없습니다.
3. 괄호 제거 로직: 여는 괄호 ( 를 스택에 넣어 '구간의 시작'을 표시하고, 닫는 괄호 ) 를 만나면 해당 구간을 처리한 뒤 여는 괄호를 pop()으로 제거함으로써 결과에 괄호가 남지 않게 합니다.

풀이 코드

class Solution:
    def reverseParentheses(self, s: str) -> str:
        stack = []

        for x in s:
            if x == ")":
                arr = []
                while stack and stack[-1] != "(":
                    arr.append(stack.pop())

                stack.pop()
                stack += arr
            else:
                stack.append(x)

        return "".join(stack)