20. Valid Parentheses

문제

Given a string 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.

Note that an empty string is also considered valid.

예시

• Example 1:

Input: "()"
Output: true

• Example 2:

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

• Example 3:

Input: "(]"
Output: false

• Example 4:

Input: "([)]"
Output: false

• Example 5:

Input: "{[]}"
Output: true

풀이

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        k2i = {'(' : ')', '[' : ']', '{' : '}'}
        i2k = {j : i for i, j in dic.items()}

        for v in s:
            if v in k2i.keys():
                stack.append(v)
            elif v in k2i.values():
                if len(stack) == 0:
                    return False
                elif stack[-1] == i2k[v]:
                    stack.pop()
                else:
                    return False

        if len(stack) > 0:
            return False
        else:
            return True

Parentheses 는 '괄호'라는 뜻으로 소괄호, 중괄호, 대괄호의 쌍이 정확히 이뤄진 input을 찾는 문제이다. 즉, 괄호를 닫는 문자는 무조건 괄호를 여는 문자 뒤에 와야하며, 정확한 쌍이 이뤄지는 것을 확인하는 과정이 필요하다.

과정은 간단하다. 여는 괄호로는 True와 False를 구분할 수 없다. 문제는 닫는 괄호가 등장할 때부터이다. 닫는 괄호가 등장하게 되면 바로 전에 들어온 문자가 해당 괄호의 여는 괄호인지 확인해야 하며, 쌍이 일치하면 pop() 으로 삭제, 그렇지 않으면 바로 False를 반환하면 된다. 여기서 pop() 으로 삭제를 해주는 이유는 다음 닫는 괄호가 나타났을 때 쌍이 일치하는 여부를 확인하기 위해서 stack의 마지막 원소와 비교해주기 때문이다.

마지막으로 문자를 쌓는 stack 리스트에 원소가 남아있으면 쌍이 일치한 경우가 아니기 때문에 False를, stack이 빈 리스트이면 True를 반환한다.

결과

76 / 76 test cases passed.
Status: Accepted
Runtime: 40 ms
Memory Usage: 13.8 MB