[리트코드 32] 가장 긴 유효 괄호 부분 문자열 — 양방향 균형 카운트

원제: Longest Valid Parentheses

문제 요약

문자열 s에서 괄호가 올바르게 짝지어진 연속 부분 문자열 중 가장 긴 길이를 반환합니다. 제출 코드는 왼쪽에서 오른쪽, 이어서 오른쪽에서 왼쪽으로 훑으며 유효한 구간의 길이를 갱신합니다.

조건과 입출력

문자열에는 (와 )만 들어갑니다. 0 <= s.length <= 3 * 10^4이며, s[i]는 ( 또는 )입니다. 원문 예제: s = "(()"의 출력은 2, s = ")()())"의 출력은 4, s = ""의 출력은 0입니다. 첫 예제의 가장 긴 구간은 "()", 둘째 예제의 가장 긴 구간은 "()()"입니다.

예제와 문제 자료

원문 예제 중 s = ")()())"에서는 "()()"가 유효한 연속 부분 문자열이므로 4를 반환합니다. 빈 문자열 s = ""에서는 확인할 구간이 없어 0을 반환합니다.

풀이 아이디어

cnt는 각 방향으로 읽을 때의 괄호 균형을 셉니다. 한 방향만 훑으면 한 종류의 괄호가 남는 구간이 균형 조건을 만족하지 못해 놓칠 수 있으므로 두 방향을 모두 검사합니다. 왼쪽에서 오른쪽으로 읽을 때 (는 cnt를 늘리고 )는 줄입니다. cnt < 0이면 현재 구간에서 닫는 괄호가 여는 괄호보다 많으므로, 그 앞부분을 포함한 유효 구간은 만들 수 없습니다. 따라서 cnt를 초기화하고 다음 위치를 새 시작점으로 둡니다. cnt == 0일 때는 구간 안의 여는 괄호와 닫는 괄호 수가 같고, 앞서 음수가 된 적도 없으므로 구간 전체가 유효합니다. 반대 방향 순회는 여는 괄호가 남는 경우를 같은 원리로 걸러냅니다.

코드의 핵심

첫 순회에서 tmp는 현재 구간의 시작 인덱스입니다. 균형이 0이 되면 i - tmp + 1로 구간 길이를 계산해 answer와 비교하고, 균형이 음수가 되면 tmp = i + 1로 다음 위치부터 다시 셉니다. 둘째 순회 전에는 cnt = 0, tmp = n - 1로 초기화합니다. 역방향에서는 )가 균형을 늘리고 (가 줄입니다. 균형이 음수가 되면 tmp = i - 1로 구간의 오른쪽 경계를 갱신하며, 균형이 0이면 tmp - i + 1을 검사합니다.

코드 추적: s = ")()())"의 첫 순회에서는 인덱스 0의 )에서 균형이 음수가 되어 시작점을 1로 옮깁니다. 인덱스 2에서 3까지 "()"의 균형이 0이 되어 길이 2를 기록하고, 인덱스 4에서 5까지 "()"에서도 길이 2를 기록합니다. 역순 순회에서는 인덱스 1부터 4까지 "()()"를 만나 균형이 0이 되므로 길이 4를 기록하고 반환합니다.

제출 코드

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        cnt = 0
        tmp = 0
        n = len(s)
        answer = 0
        for i in range(n):
            if s[i] == '(':
                cnt += 1
            else:
                cnt -= 1

            if cnt == 0:
                answer = max(answer, i - tmp + 1)

            elif cnt < 0:
                cnt = 0
                tmp = i + 1

        cnt = 0
        tmp = n - 1

        for i in range(n - 1, -1, -1):
            if s[i] == ')':
                cnt += 1
            else:
                cnt -= 1

            if cnt == 0:
                answer = max(answer, tmp - i + 1)

            elif cnt < 0:
                cnt = 0
                tmp = i - 1

        return answer

복잡도

n을 len(s)라고 하면 두 순회가 각각 문자열을 한 번씩 검사하므로 시간 복잡도는 O(n)입니다. cnt, tmp, answer 외에 입력 크기에 비례하는 자료구조를 만들지 않으므로 보조 공간은 O(1)입니다. 반환값은 정수 하나이므로 결과 저장 공간도 O(1)입니다.

복습 포인트

answer는 두 순회에서 공통으로 갱신되므로 어느 방향에서 발견한 구간이든 최댓값에 반영됩니다. 빈 문자열에서는 두 반복문이 실행되지 않아 초기값 0이 반환됩니다. 두 방향을 모두 검사하는 것이 이 코드에서 한쪽 방향으로 놓칠 수 있는 괄호 불균형을 보완하는 핵심입니다.

출처

문제 원문