[Python] leetcode | 20. Valid Parentheses 괄호 짝 맞추기 | Stack

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.

Example 1:

Input: s = "()"
Output: true

Example 2:

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

Example 3:

Input: s = "(]"
Output: false

 

Constraints:

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

 

(), [], {}이 서로 짝을 이루면 true, 아니면 false를 반환하는 함수를 완성해야 한다.

전에 백준에서 ()로만 이루어진 배열을 스택으로 풀었던 기억이 나서

"스택으로 풀어야겠다!!" 생각은 했는데

괄호가 세 종류라 경우의 수가 너무 많아서 어떻게 풀어야 할지 난감했다..

 

당연 답을 보고 푸는 것이 좋지 않은 습관이라는 것을 알고 있지만,

지금은 처음 배워 가는 단계이기에 방법을 참고했다.

 

핵심은 Stack과 딕셔너리를 사용하는 것이었다.

 

class Solution:
    def isValid(self, s: str) -> bool:
        stk=[]
        
        brackets = {')': '(', '}': '{', ']': '['}
        # 딕셔너리로 괄호 짝을 맞춘다
        for char in s:
            if char in '({[': # 여는 괄호인 경우
                stk.append(char) # 여는 괄호면 스택에 저장한다
            elif char in ')}]': # 닫는 괄호인 경우
                if not stk or brackets[char] != stk.pop(): # 스택이 비어있거나 현재 괄호와 매칭되는 여는 괄호가 스택의 top에 있는 경우
                    return False
        return not stk # 스택이 비어있어야 true

 

많이 배웠다..

다음에 혼자 다시 풀어봐야겠다.