03/20 코딩테스트 문제풀이 - 32. Longest Valid Parentheses (Leetcode) ⭐⭐⭐

문제

• Leetcode 알고리즘 문제
• 32. Longest Valid Parentheses (Hard)
• 문제 내용 : [링크]

---

내가 작성한 코드

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        stack = []
        length = 0
        max_length = 0
        for i in range(len(s)):
            if s[i] == "(":
                stack.append([i, s[i]])

            elif s[i] == ")":
                if stack and stack[-1][1] == '(':
                    stack.pop()
                    if stack:
                        length = i - stack[-1][0]
                    else:
                        length = i +1
                else: 
                    stack.append([i, s[i]])

            if length > max_length:
                max_length = length

        return max_length
        

---

• 가장 긴 유효 parentheses 괄호 묶음을 구하는 문제이다.

• 짝을 매칭하는 문제이므로, stack 풀이로 접근한다.

• 문자열 s를 for문을 통해 탐색한다.

• ( 가 나오면, 인덱스와 함께 stack 에 append 한다.

• ) 가 나올 때 몇 가지 확인 사항이 있다.

1. stack이 비어있지 않고, stack[-1] 값이 ( 이면, 짝을 이루는 관계이므로 stack.pop() 해 준다.
   1-1. 이후, stack에 값이 남아있다면, length를 업데이트 해 준다.
   이 때, length의 길이는 i-stack[-1][0]이다.
   1-2. 이후, stack이 비어있다면, length는 i+1 이다.

2. stack이 비어있거나, stack[-1] 값이 ) 이면, [i, s[i]]를 append 해 준다.

• max_length와 length 비교를 통해 max_length 를 업데이트 해준다.

• max_length를 return 한다.

---

⭐⭐⭐

• 짝을 찾는 문제는 stack으로 접근 good!

• stack 문제에서는 그 값과 인덱스가 같이 사용되는 경우가 많다.

• stack에 요소가 남아있는 지, 아닌 지 구분을 통해 parentheses 완성의 여부를 확인(어디까지 연속적인 parentheses 인지 확인)하는 아이디어 확인!