Python 스택 활용법: 가장 긴 유효한 괄호(Valid Parentheses) 찾기

문자열이 주어졌을 때, 그 안에서 가장 긴 유효한(well-formed) 괄호의 길이를 구하는 문제를 살펴보겠습니다. 예를 들어 입력 문자열이 "))(())())" 라면, 가장 긴 유효한 부분 문자열은 "(())()" 이므로 결과는 6이 됩니다.

해결 접근 방식

이 문제는 스택(Stack) 자료구조를 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 여는 괄호의 인덱스를 스택에 저장하고, 닫는 괄호가 나올 때마다 짝이 맞는지 확인하는 것입니다.

알고리즘 단계

스택을 생성하고 초기값으로 -1을 삽입합니다. 이 값은 계산 기준점 역할을 하며, 정답 변수 ans := 0으로 초기화합니다.
i를 0부터 문자열 길이 - 1까지 반복합니다.
- s[i]가 여는 괄호 '('라면 해당 인덱스 i를 스택에 삽입합니다.
- 그렇지 않은 경우(닫는 괄호 ')'):
  - 스택이 비어 있지 않고, 스택 최상단 값이 -1이 아니며, s[스택 최상단]이 여는 괄호라면
    - 스택에서 최상단 요소를 제거(pop)합니다.
    - ans := max(ans, i - 스택 최상단 값)으로 갱신합니다.
  - 그 외의 경우에는 현재 인덱스 i를 스택에 삽입합니다.
반복이 끝나면 ans를 반환합니다.

예제 코드

아래 파이썬 구현을 통해 동작 방식을 더 쉽게 이해할 수 있습니다.

class Solution(object):
    def longestValidParentheses(self, s):
        stack = [-1]
        ans = 0
        for i in range(len(s)):
            if s[i] == "(":
                stack.append(i)
            else:
                if stack and stack[-1] != -1 and s[stack[-1]] == "(":
                    stack.pop()
                    ans = max(ans, i - stack[-1])
                else:
                    stack.append(i)
        return ans

ob = Solution()
print(ob.longestValidParentheses("))(())())"))

입력

"))(())())"

출력

동작 원리 설명

스택에 처음 넣는 -1은 '마지막으로 매칭되지 않은 위치'를 나타내는 기준값입니다. 닫는 괄호를 만났을 때 스택 위에 여는 괄호가 있다면 한 쌍이 완성된 것이므로 pop하고, 현재 위치에서 새로운 스택 최상단까지의 거리가 곧 유효한 괄호의 길이가 됩니다. 만약 짝이 맞지 않는 닫는 괄호라면 그 인덱스를 스택에 push하여 이후 길이 계산의 새로운 기준점으로 사용합니다.

이 알고리즘은 모든 문자를 한 번씩만 순회하므로 시간 복잡도는 O(n), 공간 복잡도 역시 최악의 경우 O(n)입니다.