[DSA][Stack] 01. Valid Parentheses

LeetCode 20

 

01. Valid Parentheses

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
3. Every close bracket has a corresponding open bracket of the same type.

 

[질문하기]

- 문자열에 공백 등 다른 문자열이 포함될 수 있나요?

- 빈 문자열은 유효한 입력인가요? YES

 

 

[아이디어]

- stack과 hash를 이용하여 괄호의 짝을 매칭해주자.

 

[풀이 1] Stack

class Solution:
    def isValid(self, s: str) -> bool:
        if len(s) % 2 == 1:
            return False

        Pmap = {'(':')', '{':'}', '[':']'}
        stack = []

        for c in s:
            if c == '(' or c == '{' or c == '[':
                stack.append(c)
            elif not stack or Pmap[stack.pop()] != c:
                return False
        return False if stack else True

우선 문자열이 유효하려면 모든 괄호가 짝을 이루어야 하기 때문에, 문자열이 홀수인 경우는 바로 False 처리를 해준다.

그 후, 여는 괄호는 stack에 넣고, 닫는 괄호가 나오면 stack에 가장 마지막으로 쌓인 문자가 짝꿍인지를 확인한다.

괄호의 매칭을 쉽게 하기 위해, 닫는 괄호를 키로 하고 여는 괄호를 값으로 갖는 dictionary를 사용하면 비교를 간단히 할 수 있다.

 

이때 주의할 점(edge case)은 스택이 비어 있는 상태에서 닫는 괄호가 나온 경우, 잘못된 입력이므로 바로 False를 반환해야 하고 문자열을 다 순회한 후에도 스택에 값이 남아 있다면, 이는 짝이 맞지 않은 여는 괄호들이 남아 있다는 뜻이므로 역시 False를 반환해야 한다.

 

⏱️ 시간복잡도

문자열을 한 번만 순회하면서 스택에 append와 pop 연산을 하기 때문에 시간 복잡도는 O(n)

🧠 공간복잡도

스택에는 최대 문자열의 절반(여는 괄호 수)만큼 쌓일 수 있으므로 공간 복잡도도 O(n)