[파이썬] 리트코드 20. Valid Parentheses 풀이

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

Valid Parentheses - LeetCode

스택을 이용하는 대표적인 문제다. 큐의 경우 데크를 이용하여 푸는 것이 속도 면에서 이득이지만, 스택은 리스트로도 충분히 구현할 수 있고, 시간에서 큰 차이가 발생하지 않는다. 실제로 이 문제를 리스트로 풀 때와 데크를 이용해서 풀 때 걸리는 시간은 차이가 없다. 

 

1. 괄호 요소를 검사하기 위해 매핑을 이용했다. 키 ')'의 값은 '('가 된다 

2. 문자열 s 안의 각 요소 i에 대해 

    - 만약 i가 테이블 안에 없다면 스택에 쌓아준다 

    - 따라서 '(', '{', '['과 다른 비정상적인 입력값들이 스택에 쌓이게 된다 

3. 스택이 비어있지 않거나 테이블의 값이 스택에서 꺼낸 값과 같지 않다면 False 반환 

    - s = ()이라면 table[')']는 '('가 될 것이고, 스택의 마지막 요소인 '('이 pop될 것이다 

4. 스택이 비어있으면 True, 비어있지 않으면 False를 출력한다 

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

<참고>

https://g.co/kgs/dxyfp7

파이썬 알고리즘 인터뷰