[LeetCode] #20. Valid Parentheses

#20. 유효한 괄호

문제

문제 링크

괄호들로 이루어진 문자열이 주어졌을 때, 올바른 괄호인지 검사한다.
괄호 종류에는 (, ), {, }, [, ]가 있으며, 괄호는 열리고 닫혀야 한다.

풀이

입력으로 들어오는 열림 모양의 괄호를 스택에 하나씩 넣고, 닫힘 모양의 괄호와 짝이 맞으면 스택에서 괄호를 하나씩 뺀다.
파이썬의 리스트를 사용해 스택을 구현했고 요소를 넣는 연산은 append(), 요소를 제거하는 연산은 pop()을 사용했다.

0) 괄호의 짝을 맞추기 위해 딕셔너리 dict를 미리 정의했다. dict = {닫힌 괄호 : 열린 괄호} 형태로 선언하면 dict.keys()에는 닫힌 괄호가, dict.values()에는 열린 괄호가 들어간다.
따라서 조건문 if char in dict는 닫힌 괄호일때만 만족한다.
1) 입력 문자열 s길이만큼 반복하면서:
2) 열림 모양의 괄호는 stack리스트에 넣는다.
3) 닫힘 모양의 괄호는 stack리스트에 괄호가 들어있고, stack리스트의 맨 마지막 요소와 짝이 맞는 괄호라면: stack리스트에서 제거한다.

코드

github

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        dict = {")" : "(", "}" : "{", "]" : "["}
        for char in s:
            # 닫힌 괄호
            if char in dict:
                if stack and stack[-1] == dict[char]:
                    stack.pop()
                else:
                    return False
            # 열린 괄호
            else:
                stack.append(char)
        return stack == []

참고한 강의 : NeetCode