[LeetCode] Valid Parentheses

문제 링크 >> https://leetcode.com/problems/valid-parentheses/

 

 

📋 문제

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.

 

 

👉 입출력

Example 1:

Input: s = "()"
Output: true

Example 2:

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

Example 3:

Input: s = "(]"
Output: false

 

 

📝 풀이

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

 

괄호의 종류가 세 가지라 조금 까다로웠던 문제였다.

먼저 괄호가 세 가지이기 때문에 닫힌 괄호를 key로 가지는 brackets 딕셔너리를 선언했다.

 

입력으로 주어진 s를 순회하며 각 문자를 살핀다.

만약 i가 brackets.keys()에 없다면, 그러니까 i가 여는 괄호라면 stack에 넣는다.

 

i가 닫는 괄호이면 먼저 stack의 길이를 확인한다.

stack이 비어있는데 i가 닫는 괄호이면 바로 False를 리턴해 괄호가 유효하지 않다는 것을 알린다.

stack이 비어있지 않다면 stack에서 pop하고 이를 딕셔너리의 value와 확인해 알맞은 괄호가 아니라면 또 False를 리턴한다.

 

for문의 순회가 끝났다면 stack의 길이를 확인한다.

이때 빈 스택이라면 s는 유효한 괄호들로 이루어졌다는 뜻이고 스택이 비어있지 않다면 s가 유효한 괄호가 아니라는 뜻이다.