[파이썬 알고리즘] 유효한 괄호짝

유효한 괄호

리트코드로 풀러 가기

괄호로 된 입력값이 올바른지 판별하라.
열린 괄호들은 반드시 같은 타입의 괄호로 닫혀야 한다.
열린 괄호들은 정확한 순서로 닫혀야 한다.

Input: s = "()"
Output: true

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

Input: s = "(]"
Output: false

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

파이썬의 리스트는 스택 연산 push, pop이 O(1)에 작동하기 때문에 스택 문제를 풀 때 사용해도 성능에 큰 문제가 없다.

스택에의 일치 여부 판별

스택에 입력값을 넣어둔 뒤, ), }, ] 등 괄호의 마침이 올 때 pop하여 짝이 맞는지를 검사하면서 풀 수 있다.

def isValid(self, s: str) -> bool:
    stack = []
    table = {
        ')': '(',
        '}': '{',
        ']': '[',
    }
    
    for char in s:
        if char not in table:
            stack.append(char)
        elif not stack or table[char] != stack.pop():
            return False
    return len(stack) == 0

비정상적인 테스트 케이스들을 통과하기 위해 입력값에 따른 예외 처리를 해주는 것 또한 중요하다.