32. Longest Valid Parentheses

존재할 수 있는 괄호쌍 중 가장 긴 길이를 찾는 문제이다.

 

구상한 방법

1. '(' 갯수보다 ')' 가 많으면 모든 count 초기화.
2. '(' 갯수와 ')' 갯수가 같아지는 시점에 max값과 비교하여 크면 max에 대입.

이런 식으로 한다면 ' ( ) ( ( ( ) ) '  과 같은 경우

->	(	)	(	(	(	)	)
( 갯수	1	1	2	3	4	4	4
) 갯수	0	1	1	1	1	2	3

Max = 2 개가 된다. 하지만 답은 Max = 4 이다. (초록 부분)

( 갯수보다 ) 갯수가 더 적은 경우 왼쪽에 빨간 답으로 만들어진 괄호쌍이 포함되지 않는 것은 좋지만,

새롭게 초록색 부분이 답이 되지 못한다.

 

솔루션을 본 결과, 이 수행을 거꾸로 한번 더 해주면 답을 구할 수 있다.

 

(	)	(	(	(	)	)	<-
1	0	3	2	1	0	0	( 갯수
1	1	2	2	2	2	1	) 갯수

거꾸로 수행하므로, ) 갯수보다 ( 갯수가 많아지면 카운팅을 초기화 시킨다.

 

 

정말 신선한 방법이라고 생각된다.

한번에 처리할 수 없으면 거꾸로 한번 더 수행하여 할 수 있다는 방법을 깨닫게 해주었다.

 

 ** 또한 ' reversed(range(x)) '를 쓰면 거꾸로 숫자가 흐른다. **

( range(len(x),0,-1)을 사용할 경우 0을 포함하지 않게된다. )

 

소스코드

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        op = 0
        cl = 0
        result = 0
        for i in range(len(s)):
            if s[i] == "(":
                op += 1
            elif s[i] == ")":
                cl += 1
            if op == cl:
                if result < op + cl:
                    result = op + cl
            elif op < cl:
                op = 0
                cl = 0
                
        op = 0
        cl = 0
        for i in reversed(range(len(s))):
            if s[i] == "(":
                op += 1
            elif s[i] == ")":
                cl += 1
            if op == cl:
                if result < op + cl:
                    result = op + cl
            elif op > cl:
                op = 0
                cl = 0
                
        return result