[leetcode 매일 풀기] 32 longest valid parentheses

오늘 리뷰할 문제는 leetcode 32번 longest valida parentheses이다.

 

https://leetcode.com/problems/longest-valid-parentheses/

Longest Valid Parentheses - LeetCode

 

문제는 여태 풀었던 다른 문제들보다 직관적인데.

 

(와 ) 로만 이루어진 문자열에서, 가장 긴 valid한 괄호의 길이를 찾는 것이다.

valid한 정의를 코딩을 해야하니 다시 생각해보면

string에서 (의 길이와, )의 길이가 같아야하고, 어떤 위치에서든 )의 갯수보다 (의 개수가 같거나 적어야 한다는 뜻이다.

 

생각보다 적절한 구현을 찾지 못해서 이번에도 solution을 보고 푸는 방법을 업데이트 했다.

 

풀이를 보니 stack을 사용하여 (의 위치를 저장하고, )이 나올 때마다 길이를 최대길이와 비교하는 식으로 짜면 깔끔하게 시간 복잡도 O(문자열의 길이)로 짤 수 있다는 풀이를 보고 감탄했다.

 

아래는 최종적으로 짠 코드 스니펫이다.

 

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        stack = [-1]
        res = 0
        for i, c in enumerate(s):
            if c == "(":
                stack.append(i)
            else:
                stack.pop()
                if not stack:
                    stack.append(i)
                else:
                    res = max(res, i - stack[-1])

        return res


assert Solution().longestValidParentheses("(()") == 2
assert Solution().longestValidParentheses(")()())") == 4
assert Solution().longestValidParentheses("") == 0

 

 

실제로 결과는 위와 같이 나왔다.

 

다른 사람의 코드를 보면서 알게 된 것은.

편의를 위해서 enumerate를 사용해서 코드를 자주 짰는데. 가독성 측면에서는 좋지면 performance 측면에서는 range(len(s))를 사용하고, 직접 접근하는게 더 빠르다는 것을 알 수 있었다.

enumerate를 range(len(s))로 바꾸니 아래와 같이 runtime이 조금 더 줄어드는 것을 확인할 수 있었다.