[리트코드] Valid Parentheses(python)

리트코드, Valid Parentheses_유효한 괄호

 

TL;DR

• 스택(stack)

문제 분석

1. 주어진 괄호 문자('(', ')', '{', '}', '[', ']')를 포함하고 있는 문자열 s가 유효한지를 판별해야 한다.
2. 열린 괄호는 같은 종류의 닫힌 괄호와 붙어있어야 한다.
3. 열린 괄호와 같은 종류의 닫힌 괄호는 정확한 순서로 되어 있어야 한다.

 

- 1 : 해결해야 하는 문제에 대해서 설명하고 있다.

- 2 ~ 3 : 같은 종류의 열린 괄호와 닫힌 괄호로만 이루어져있는 문자열이 올바른 괄호 문자라는 것을 설명하고 있다.

입출력 형태

입출력 예시

 

- 입출력 예시를 통해 문제에서 말하는 유효한 괄호문자의 조건을 확인할 수 있다.

- 예시 1과 예시 2는 서로 같은 종류의 괄호들이 올바르게 잘 배치되어 있다.

- 반면 예시 3의 경우 열리는 괄호 기호는 (지만 닫히는 기호는 ]이기 때문에 유효하지 않다.

풀이

class Solution:
    def isValid(self, s: str) -> bool:
        if len(s) == 0 or len(s) == 1:
            return False
        
        brackets = []
        
        for bracket in s:
            if len(brackets) == 0:
                brackets.append(bracket)
                continue
            
            brackets.append(bracket)
            item = brackets.pop()
            top = brackets.pop()
            
            if (top == '(' and item == ')') or (top == '{' and item == '}') or (top == '[' and item == ']'):
                continue
            else:
                brackets.append(top)
                brackets.append(item)
                
                
        return len(brackets) == 0

 

- 후입선출(Last In, First Out)의 특징을 갖고 있는 스택(Stack)을 활용하여 문제를 해결할 수 있다.

- 파이썬에서는 리스트가 스택의 역할을 수행할 수 있다.

- 괄호 문자를 스택에 넣고, 방금 넣은 괄호와 마지막에 넣은 괄호를 빼내서 비교한다.

- 만약 두 괄호 문자가 같은 종류이고 서로 열리고 닫힌 괄호라면 그대로 진행한다.

- 그렇지 않을 경우에는 다시 스택에 넣는다.

- 만약 모든 판별이 잘 진행된 경우에는 스택의 길이가 0이 되고 그렇지 않을 경우에는 짝을 찾지 못한 괄호문자가 남게 된다. 따라서 저런 형태로 작성해주면 된다.

 

개선된 풀이

- 하지만 위 방법은 파이썬스럽지 못하다. 이 코드를 개선하면 아래와 같이 작성할 수 있다.

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

 

- 열린 괄호일 경우에 스택에 넣고, 닫힌 괄호일 경우에는 스택에 들어있는 가장 최근의 아이템(top)과 비교하여 같은 종류가 아닐 경우 거짓을 반환하는 방식으로 풀면 된다.

- dictionary를 통해 각 괄호 쌍을 묶어서 표현하면 조건을 간단하게 표현할 수 있다.