[Leet Code] Valid Parenthesis

문제 출처

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:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
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 '()[]{}'.

풀이

 

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

        for char in s:
            if char in mapping.values():
                stack.append(char)
            elif char in mapping.keys():
                if not stack or mapping[char] != stack.pop():
                    return False
        
        return not stack

괄호 짝을 맞추는 문제입니다. 괄호로 이루어진 string이 괄호 짝이 맞지 않으면 false, 짝이 맞으면 true를 return해야 합니다.
우선 False일 경우는 두 가지로 정리됩니다.
1.  ) , }, ] 가 (, {, [ 보다 먼저 나왔을 경우

2. (, {, [  가 먼저 나왔지만, 바로 다음에 짝을 이루는 닫는 괄호라 나오지 않을 경우

이제 문제를 해결하기 위해서는
괄호별로 여닫는 기호를 mapping한 dictionary를 생성합니다.

예시답변에사는 닫는 괄호를 key, 여는 괄호를 value로 mapping 했습니다.

이제 string안의 각 문자를 순회합니다.
1. value(여는 괄호) 일 경우, 다음에 짝이 맞는 닫는 괄호가 나오는지 확인하기 위해 stack에 임시로 append 해놓습니다.

2. key(닫는 괄호)일 경우,
a. stack이 비어 있는지 확인합니다(닫는 괄호가 처음 나온 것이니 false)
b. mapping 되어 있는 짝이 stack에 있는 문자와 맞는지 확인합니다( 다르면 false)


stack을 만들어 string 의 각 문자를 하나씩 순회하며 dictionary와 비교하게 하면 됩니다.

stack은 Last in First Out 특징이 있습니다. .pop을 이용하야 마지막에 추가된 문자부터 꺼내어 비교하게 됩니다.