[LeetCode] #20. Valid Parentheses (python)

문제

https://leetcode.com/problems/valid-parentheses/

Valid Parentheses - LeetCode

괄호가 유효한지 확인하는 문제다. 괄호가 같은 종류로 잘 닫혔는지 확인하면 된다.

 

예시 입출력

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

 

 

풀이

 

내 풀이

class Solution:
    def isValid(self, s: str) -> bool:
        
        stack=[]
        start=['(','{','[']
        end=[')','}',']']
        
        for i in s:
            if stack:
                if i in end and stack[-1] in start:
                    if end.index(i)==start.index(stack[-1]):
                        del stack[-1]
                    else:
                        stack.append(i)
                else:
                    stack.append(i)
            else:
                stack.append(i)
        
        if stack:
            return False
        else: return True

여는 괄호랑 닫는 괄호를 미리 리스트에 넣어두었다. 현재 문자가 닫는 괄호고 스택의 가장 위에 있는 값이 여는 괄호고 닫는 괄호와 같은 종류면 스택 값을 지운다. 그렇지 않은 경우는 스택에 추가한다. 

 

 

책 풀이

class Solution:
    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

책에서는 딕셔너리를 활용해 괄호 종류가 일치하는지 확인했다. 

첫번째 조건인 char not in table은 현재 괄호가 여는 괄호일 때 스택에 추가하라는 뜻이다.

두번째 조건은 스택이 비었거나 괄호가 맞게 닫히지 않았으면 False를 return 하라는 뜻이다.

반복문이 다 끝나고 스택이 비었으면 True가 return 된다.

그리고 마지막 return에서 저렇게 조건을 쓴 게 신기했다. 나였으면 if를 사용해서 조건문쓰고 true, false 나눴을텐데 훨씬 깔끔하다.

 

 

참고한 책 : 파이썬 알고리즘 인터뷰