[Python] Longest Valid Parentheses

Hard 난이도 Acceptence 30% 문제

 

입련된 문자열에서 유효한 최대길이의 괄호쌍의 길이를 구하는 문제

 

문자열의 길이만큼 0으로 문자열을 만들었고, 왼쪽 괄호일경우 인덱스를 더하고, 오른쪽괄호일 경우 왼쪽괄호와 오른쪽괄호 위치의 값을 1로 만든다.

모든 유효한 괄호쌍을 1로 유효하지 않은 괄호는 0으로 저장한 문자열중 1을 max로 가지고 있는 subarray를 정답으로 구한다.

 

class Solution:
    def longestValidParentheses(self, s):
        stack = []
        a = ['0'] * len(s)

        for i in range(len(s)):
            if s[i] == '(':
                stack.append(i)
            else:
                if not stack:
                    next
                else:
                    index = stack.pop()
                    a[i] = '1' # for the ')'
                    a[index] = '1' # for the '('
        longest = max(''.join(a).split('0')).count('1')
        return longest