View in English →

Code › algorithm-study

LeetCode 20 - Valid Parentheses

여는 괄호를 Stack에 저장하고 닫는 괄호의 짝과 순서를 확인하는 Python 풀이

algorithmleetcodestackstringpythonlearning

오랜만에 다시 easy 문제로 찾아왔다. 요즘 정리할것이 많아서 정신없지만 그래도 흐름을 좀 이어가보려고 한다. 먼저 이 문제는 괄호로만 이루어진 문자열이 주어졌을 때, 모든 괄호가 올바른 종류와 순서로 닫히는지 확인하는 Easy 문제다. 여는 괄호를 순서대로 저장한 뒤 가장 최근에 열린 괄호부터 닫혀야 하므로 Stack을 사용했다.

문제 링크 & 설명

  • 문제 링크: 20. Valid Parentheses
  • 요약: 소괄호, 중괄호, 대괄호로 구성된 문자열이 올바르게 열리고 닫혔으면 true를 반환한다.

괄호의 개수가 맞다고 유효한 문자열이 아닌것에 주의해야한다. ([)]는 여는 괄호와 닫는 괄호의 수가 같지만, 마지막에 연 괄호부터 짝을 맞춰 닫아야 한다는 규칙에 어긋난다!

"()"      -> true
"()[]{}"  -> true
"(]"      -> false
"([)]"    -> false
"{[]}"    -> true

여는 괄호가 나오면 아직 닫히지 않은 상태로 저장하고, 닫는 괄호가 나오면 가장 최근에 저장한 여는 괄호와 짝이 맞는지 확인해야 한다.

접근 방법

문자열을 왼쪽부터 순회하면서 여는 괄호를 Stack에 넣었다. 닫는 괄호를 만나면 Stack의 마지막 원소가 현재 괄호와 짝을 이루는지 확인하고, 맞으면 마지막 원소를 제거한다.

if ch == '(' or ch == '{' or ch == '[':
    stack.append(ch)
elif stack and self.is_pair(stack[-1], ch):
    stack.pop()
else:
    return False

Stack은 나중에 들어온 값이 먼저 나오는 LIFO 구조다. ([까지 읽었다면 [가 (보다 나중에 열렸으므로 ]가 먼저 나와야 한다. Stack의 마지막 원소만 확인하면 이 순서를 그대로 검증할 수 있다.

괄호의 조합을 확인하는 부분은 is_pair 메서드로 분리했다.

def is_pair(self, open_bracket, close_bracket):
    return (
        (open_bracket == '(' and close_bracket == ')')
        or (open_bracket == '{' and close_bracket == '}')
        or (open_bracket == '[' and close_bracket == ']')
    )

모든 문자를 문제없이 처리했더라도 Stack이 비어 있는지 마지막에 확인해야 한다. ((처럼 여는 괄호만 남은 문자열은 반복문 안에서 실패하지 않지만, 아직 닫히지 않은 괄호가 있으므로 false가 되어야 한다.

트러블 슈팅

닫는 괄호가 나왔을 때 Stack의 마지막 값을 바로 읽으면, ")"처럼 닫는 괄호가 먼저 등장하는 입력에서 존재하지 않는 원소에 접근하게 된다. 그래서 짝을 비교하기 전에 Stack에 원소가 있는지 먼저 확인했다.

elif stack and self.is_pair(stack[-1], ch):

Python의 and는 왼쪽 조건이 false이면 오른쪽 조건을 계산하지 않는다. Stack이 비어 있으면 stack[-1]을 읽지 않고 else로 이동해 false를 반환한다.

또한 짝의 종류만 확인하고 순서를 무시하면 ([)]를 처리할 수 없다. 첫 번째 닫는 괄호 )가 나왔을 때 Stack에는 (와 [가 들어 있고, 마지막 원소인 [와 )는 짝이 아니다. 이 지점에서 바로 false를 반환해야 괄호의 중첩 순서까지 검증할 수 있다.

복잡도 분석

문자열의 길이를 n이라고 하자.

  • 시간 복잡도: O(n)

    • 문자열의 각 문자를 한 번씩 확인한다. Stack의 append와 pop, 마지막 원소 확인은 모두 상수 시간이다.

  • 공간 복잡도: O(n)

    • 최악의 경우 문자열의 모든 문자가 여는 괄호일 수 있어서, Stack에 n개의 문자가 저장된다.

구현 코드

class Solution:
    def is_pair(self, open_bracket, close_bracket):
        return (
            (open_bracket == '(' and close_bracket == ')')
            or (open_bracket == '{' and close_bracket == '}')
            or (open_bracket == '[' and close_bracket == ']')
        )

    def isValid(self, s: str) -> bool:
        stack = []

        for ch in s:
            if ch == '(' or ch == '{' or ch == '[':
                stack.append(ch)
            elif stack and self.is_pair(stack[-1], ch):
                stack.pop()
            else:
                return False

        return not stack

요약 및 회고

이 문제에서는 두가지만 잘 살펴보면 된다, 짝이 맞는지와 마지막에 loop를 돌고 나서 스택이 비었는지이다. 쉬운 문제도 사실 오랜만에 보면 갑자기 구현이 어떻게 되어야할지 손이 안나갈때가 있다. 그래서 반복해서 자주 풀어서 체화시키는 것이 중요한 것 같다. 다만 단순 암기보다는 이해한 바를 반복해서 각인되도록!