링크 : https://leetcode.com/problems/valid-parentheses/

description

Given a string s containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[’ and ‘]’, determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.

Example:

Input: s = "()"
Output: true

Input: s = "()[]{}"
Output: true

Input: s = "(]"
Output: false

Input: s = "([)]"
Output: false

Input: s = "{[]}"
Output: true

Constraints

• 1 <= s.length <= 104
• s consists of parentheses only ‘()[]{}’.

작성한 코드

class Solution:
    def isValid(self, s: str) -> bool:
        OPEN = { '{': 0, '(': 1, '[': 2 }
        CLOSE = { '}': 0, ')': 1, ']': 2 }
        stack = []
        
        for ch in s:
            if ch in [ '{', '(', '['] : stack.append(ch)
            else :
                if len(stack) == 0 : return False
                openBracket = stack.pop()
                if OPEN[openBracket] != CLOSE[ch] : return False
        
        if len(stack) > 0 : return False
        return True

설명

파이썬의 딕셔너리를 활용해서 코드를 보기좋게 쓰려고 했다. 각 쌍별로 타입 넘버를 선언한다. 오픈 브라켓은 스택에 넣고 클로즈 브라켓이면 pop을 하는데 그 전에 스택이 비어있다면 짝이 안맞는 것이므로 False를 리턴한다. 1개 이상이면 pop하고 타입이 다르면 False를 리턴한다. 반복문을 모두 실행하고도 스택에 브라켓이 남아있다면 짝이 안맞으므로 False 리턴.

처음에는 오픈 브라켓을 담아두는 배열을 선언했는데 생각보다 이게 메모리를 많이 잡아먹어서 빼고 if문에 바로 넣어버리니까 효율이 급 높아졌다. 쉬운 문제 좋다 하하

Runtime: 16 ms, faster than 99.89% of Python3 online submissions for Valid Parentheses.
Memory Usage: 14 MB, less than 99.22% of Python3 online submissions for Valid Parentheses.