[LeetCode] 20. Valid Parentheses

teyoung·2023년 3월 7일

LIFO stack

Algorithm with Python

목록 보기

3/4

1. 문제 이해

문제 해석

오직 '(', ')', '{', '}', '[' , ']' 6개의 Characters만을 포함하는 String s 가 주어질 때, 다음 3가지 조건을 만족하는지 판단

여는 괄호 '(' , '{' , '[' 는 각각 같은 타입의 닫는 괄호 ')' , '}' , ']' 형태로 닫혀야한다.
() , {} , [] 같은 타입의 괄호가 열리고 닫힌 다음, 다음 타입의 괄호가 열리고 닫히고… 순서가 맞아야 한다.(LIFO)
마찬가지로 닫는 괄호 ')' , '}' , ']' 는 같은 타입의 여는 괄호와 짝을 이루어야 한다.

제약 조건 해석

1 ≤ s.length ≤ 10^4,

s consist of parantheses only '()[]{}'

s.length 의 범위는 10^4 이하이므로, 문제 해결 알고리즘의 시간복잡도가 O(n^2) 이상이 되면 위험할 것 같다.
위의 제약 조건 외에는 s 에 포함될 수 있는 Characters가 '()[]{}' 한정되어 큰 어려움은 없을 것 같다.

2. 접근 방법

먼저 직관적으로 생각하기

String s 의 Characters를 순회하면서 Stack에 담는데, 닫는 괄호가 나왔다면 Stack의 Top과 비교해서 같은 Type인지 확인한다.
반복문이 종료되고 Stack에 요소가 남아있다면 False를 반환한다.
Stack이 비워졌다면 True를 반환한다.

활용한 자료구조 & 알고리즘

Stack
- 마지막으로 열린 괄호가 닫힌 다음 이전에 열렸던 괄호가 닫히는 순서가 지켜져야하기 때문에 LIFO 순서의 알고리즘이 필요하다.

3. 코드 설계 및 구현

작성한 코드

class Solution(object):

    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        
        # 1. Stack 초기화
        stack = []

        # 2. String s를 순회하면서 
        for i in s:
            # 2-1. 만약 여는 괄호라면 stack에 push
            if i =='(' or i == '{' or i == '[':
                stack.append(i)
            # 2-2-1. 닫는 괄호라면 stack의 탑과 현재 값의 괄호타입이 일치하는지 확인
            else:
                top = stack[len(stack) - 1]
                # 2-2-2. 괄호의 순서와 타입이 일치하면 stack.pop()
                if i == ')' and top == '(':
                    stack.pop()
                elif i == '}' and top == '{':
                    stack.pop()
                elif i == ']' and top == '[':
                    stack.pop()
        # 3-1. 스택이 모두 비워졌다면 return True
        if not stack:
            return True
        # 3-2. 아니라면 return False
        else:
            return False

Stack의 LIFO 개념을 실제로 적용해 볼 수 있는 기본적인 문제였다.
Stack.push() / Stack.pop() 둘 다 O(1) 복잡도를 갖는다.
s의 Characters를 모두 순회해야 하므로 실질적인 시간복잡도는 O(n)이다.

레퍼런스 코드

def isValid(s):
		stack = []
		for p in s:
				if p == "(":
						stack.append(")")
				elif p == "{":
						stack.append("}")
				elif p == "[":
						stack.append("]")
				elif not stack or stack.pop() != p:
						return False
		return not stack