[Leetcode] 20. Valid Parentheses

문제

https://leetcode.com/problems/valid-parentheses/description/?envType=study-plan-v2&envId=top-100-liked

풀이

자주 접했던 문제이고, 스택을 이용해서 푼 첫 풀이는 다음과 같다.

bracket_match = {')':'(', '}':'{',']':'['}

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        for bracket in s:
            if bracket in '([{':
                stack.append(bracket)
            elif not stack: # stack 비어있으면
                return False
            elif stack[-1] != bracket_match[bracket]:
                return False
            else:
                stack.pop()
        
        return not stack # stack이 비어있어야 true

이때, not stack 보다는 len(stack)==0 이 더 직관적으로 생각된다. 또한. '([{'로 되어있는 부분은 bracket_match.values()로 대체 가능하다.

그리고, stack.pop()을 조건문 체크 안에 넣어서 코드 양을 줄여보면 다음과 같이 된다.

그냥 딕셔너리에 in 연산을 사용하면 딕셔너리의 키들을 대상으로 존재를 체크한다.

bracket_match = {')':'(', '}':'{',']':'['}

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        for bracket in s:
            if bracket in bracket_match.values():
                stack.append(bracket)
            elif len(stack)==0 or stack.pop() != bracket_match[bracket]:
                return False
        
        return len(stack)==0 # stack이 비어있어야 true