[LeetCode] 20. Valid Parentheses

20. Valid Parentheses

Easy

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로 답을 리턴해야한다.

문제를 풀기전에 제한사항을 확인해보면 10^4 이기 때문에 브루투포스로 풀어도 된다. 

하지만 이 문제는 대표적인 Stack 문제이며, 모든 것을 조건으로 짜기에는 코드가 많이 복잡해진다. 

그리고 문제에서 조심해야할 것은 예외처리를 어떻게 해야할지 생각해봐야한다. 

예를들어, '([)]', '({}[(]))' 이런 예제들을 예외로 생각해서 고민해봐야한다. 

눈으로 보기에는 같은 괄호로 닫힐것 같이 생겼다.

하지만 'Open brackets must be closed in the correct order.' 문구를 보면 올바른 순서로 닫혀야된다.

이는 괄호가 열리고 중간에 짝이 없는 열린 괄호가 있으면 안된다.

닫히는 괄호가 한짝의 괄호안에 들어가야하는 것이라고 볼 수 있다. 

다시 풀이방법으로 돌아가서, 괄호를 열고 닫는것을 확인할때 O(N)으로 풀려면 Stack을 사용해야한다.

스택에 괄호를 하나씩 모두 넣으면서 확인하되 닫힌 괄호가 나타났을때 스택에 그 짝의 열린괄호가 있는지 확인한다.

조건문으로 괄호 짝들을 구별하지 않고 딕셔너리 즉 해쉬테이블로 닫는 괄호들을 키로 열린 괄호들을 벨류로 지정한다.

for 문으로 문장을 한글자씩 탐색하면서 만약에 스택이 차있고 괄호가 닫은 괄호이면 닫힌 괄호들을 저장한 딕셔너리에 있는지 확인한다.

만일 닫힌괄호의 짝이 스택 맨앞에 있다면 스택에서 제거하고 코드를 뛰어넘는다.

만일 열린괄호거나 스택이 비어있으면 괄호를 넣는다. 

이 과정을 거치면, 모든 괄호들이 닫혔을 경우 스택이 비게 된다. 

결과적으로 스택이 비어있으면 문제에서 원하는 정답이며, 스택이 안비어있으면 정답이 아니게 된다.

코드를 쉽게 짜기위해서 딕셔너리와, continue를 사용하였다. 

소스 코드

class Solution:
    def isValid(self, s: str) -> bool:
        parentheses = {
            ')' : '(',
            ']' : '[',
            '}' : '{'
        }
        stack = []
        for ch in s:
            if stack and ch in parentheses:
                if stack[-1] == parentheses[ch]:
                    stack.pop()
                    continue
            stack.append(ch)
        if stack:
            return False
        return True