[코테] 리트코드 스택,큐 20. Valid Parentheses

20. Valid Parentheses

문제 링크

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.
3. Every close bracket has a corresponding open bracket of the same type.

제한 사항

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

입출력 예 #1

1. Input: s = “()”
2. Output: true

입출력 예 #2

1. Input: s = “()[]{}”
2. Output: true

입출력 예 #3

1. Input: s = “(]”
2. Output: false

문제 풀이

스택 구조의 기초 문제로 여는 괄호면 스택에 쌓고, 닫는 괄호면 스택의 마지막 항목과 비교하여 정상인지 여부 확인

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        table = {
            ')' : '(',
            '}' : '{',
            ']' : '['
        }

        # 스텍 이용 예외 처리 및 일치 여부 판별
        for char in s :
            if char not in table :
                stack.append(char)
            elif not stack or stack.pop() != table[char] :
                return False
            
        return len(stack) == 0