(20)20. Valid Parentheses

“파이썬 알고리즘 인터뷰” + https://leetcode.com/problems/valid-parentheses/

스택과 큐 파트로 넘어왔다. 학부에서 가장 처음 배우는 자료구조가 스택과 큐가 아닌가 한다. 기본이고 단순한 구조이지만 실제 사용하지 않으면 모르는 건 매한가지다.

첫 문제는 주어진 괄호들이 올바른지 판별하는 것이다. 괄호가 올바르게 닫혔는지를 보면 된다. “()[]”과 “[{()}]”는 True이고 “[)”나 “[{}(])”는 False이다.

    def isValid1(self, s: str) -> bool:
        stack = []
        table = {
            "(": ")",
            "[": "]",
            "{": "}"
        }
        for chr in s:
            if table.get(chr):
                stack.append(chr)
            else:
                if not stack or table.get(stack.pop()) != chr:
                    return False
        if stack:
            return False
        return True

    def isValid2(self, s: str) -> bool:
        stack = []
        table = {
            ")": "(",
            "]": "[",
            "}": "{"
        }
        for char in s:
            if char not in table:
                stack.append(char)
            elif not stack or table[char] != stack.pop():
                return False
        return len(stack) == 0

isValid1이 내 풀이인데 책에서와 비슷하게 됐지만 괄호를 정의하는 딕셔너리 변수 “table”을 반대로 정의했더니 조건문이 꼬여서 바로 풀리지 않았다. 그리고 leetcode에서 예외적인 입력으로 “[“나 “]”와 같은 것들이 있어서 내 소스는 조금 지저분하게 돼버렸다.