remind는 다시 풀어볼 필요가 있어서 기록했다.

문제

• 문자열 s가 주어진다. s 는 (,)로만 이루어져 있다.
• 이때, 유효한 괄호의 최대길이값을 return하는 함수를 작성하라.

  유효한 괄호란, (())처럼 완전하게 둘러쌓여있는 괄호를 말한다.

해결 방안

• 솔직히 온짓을 다해봤다. 일단 유효괄호 접근이었기 때문에 스택으로 접근을 해봤었는데, 중간 depth 고려가 휘말려서 여러 테스트케이스에서 날라갔다.
• 그래서 살짝 찾아 봤었는데, DP로 쉽게 풀 수 있었다.
• 1. 인덱스를 스택에 저장한다.
• 2. 그리고 pop할때 스택에서 뽑은 index에 matching되었음을 확인시키고 카운트를 증가시킨다.
• 3. 그리고 맨 마지막에 더한다
• 4. 끝

끝?

코드

class Solution(object):
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        depth = 0
        stack = []
        arr = [0] * len(s)
        for i in range(len(s)) :
            if s[i] == '(' :
                stack.append(i)
            elif stack :
                arr[stack.pop()] = 1
                arr[i] = 1
        ret = 0
        tmp = 0
        for i in arr :
            if i == 1 :
                tmp +=1
                ret = max(ret,tmp)
            else :
                tmp = 0
        return ret

• 솔직히 DP가 아직 덜 체화되서 이런 활용도 있구나 정도를 깨닫게 된다... 더 힘내보자