[python] leetcode 20. Valid Parentheses

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

문제 설명

 괄호로 된 입력값이 올바른지 판별 (기본기 점검으로 좋은 문제)

문제 풀이 접근

1) 각 여는 괄호는 짝이 맞는 닫는 괄호가 있다
2) 닫는 괄호의 순서는 여는 괄호의 순서와 반대로 이루어져야 한다. 가장 마지막에 오는 여는 괄호는 가장 처음에 오는 닫는 괄호와 만나게 되고, 이런 패턴이 계속 반복된다.
   → 스택으로 접근 (LIFO)
   → 여는 괄호는 스택에 넣고, 닫는 괄호를 만나면 pop해서 짝이 맞는지 대조하는 방식
   → 짝이 맞는지 대조하는 데에 편리한 자료구조는 딕셔너리

문제 풀이

class Solution:
    def isValid(self, s: str) -> bool:
        parentheses = {
            "(" : ")",
            "{" : "}",
            "[" : "]"
        } # 괄호 짝 대조를 위한 딕셔너리
        stack = [] # 여는 괄호를 담을 stack

        for par in s:
            if par in parentheses.keys(): # 여는 괄호라면
                stack.append(par) # stack에 push
            else: # 닫는 괄호
                try:
                    op = stack.pop()
                    if parentheses[op] != par:
                        return False
                except: # 닫는 괄호로 시작하는 경우 예외처리
                    return False

        if stack: # for loop을 마쳤지만, stack에 여는 괄호가 남아있는 경우 (짝이 안맞는 경우)
            return False

        else:
            return True # for loop을 정상적으로 마치면 Valid parentheses.

        

- 간과한 테스트 케이스

 1) 여는 괄호 하나로 이루어진 경우

 2) 한 타입의 괄호로만 이루어진 경우

 정확히 말하면 1)의 경우가 2)에 속한다고 볼 수 있다. 따라서 if stack~ 부분에서 모든 예외 처리가 가능하다. 그러나 닫는 괄호로 시작하는 경우에는 첫번째 else문 안에서 error가 발생할 수 있으므로 try~except~ 문으로 예외 처리를 따로 해주었다.

 테스트 케이스를 다양하게 생각하지 못해서 꽤나 많은 시행착오를 겪었다. 리트코드는 테스트 케이스를 떠먹여줘서 좋긴 한데 다양한 테스트 케이스를 생각하는 것도 중요한 부분이라 이런 부분은 좀 더 고민을 해보도록 해야겠다.

- 좀 더 깔끔한 답안

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

        for par in s:
            if par in parentheses.keys(): # 여는 괄호라면
                stack.append(par) # stack에 push
            elif (not stack) or (parentheses[stack.pop()] != par):
                # not stack (닫는 괄호로 시작)
                # parentheses[stack.pop()] != par (여는 괄호와 닫는 괄호의 짝이 맞지 않을 때)
                return False

        # 모든 string을 다 탐색했는데 stack이 남아있는 경우에는 False
        # stack이 정상적으로 비워져 있다면 True
        # 이 모든 경우를 포괄하기 위해서는 stack의 길이가 0인지를 return하도록 함
        return len(stack) == 0

 위의 풀이가 많은 예외처리와 분기문이 있으므로 최대한 간결하게 if문을 짜보았다. 또한 return 문에서 단순히 len(stack) == 0으로 처리하도록 함.