[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.

예제 1

Input: s = "()"
Output: true

예제 2

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

예제 3

Input: s = "(]"
Output: false

조건

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

---

📌 풀이

• stack에는 여는 괄호만 쌓는다.
• dictionary는 닫는 괄호를 key로 설정했다.
• 현재 원소가 여는 괄호면 stack에 쌓고, 닫는 괄호면
  • stack 길이 체크 → 길이가 0이라면 여는 괄호가 없는데 닫는 괄호가 들어온 것이므로 return False
  • stack top에 있는 여는 괄호와 현재 원소의 pair인 여는 괄호가 동일한지 체크 → 동일하다면 stack top을 pop하고 다음 원소 검증
  • 위 두 조건에 모두 해당되지 않는다면 (]와 같이 pair가 맞지 않는 경우이므로 return False
• 마지막으로, 정상적인 pop을 거쳐 stack이 비워졌는지 체크해서 그렇다면 return True

class Solution(object):
    def isValid(self, s):
        
        stack = []

        dic = {')': '(',
                '}': '{',
                ']': '['}

        for i in s:
            if i not in dic:
                stack.append(i)

            else:
                if len(stack) == 0:
                    return 0
                elif stack[-1] == dic[i]:
                    stack.pop()
                else:
                    return 0
                
        return len(stack) == 0

• 테스트케이스 ], (), (] 각각의 시퀀스를 그려보았다.
  

런타임 앵간 괜찮게 푼 듯 ㅎ