[스택] Leet Code 20. Valid Parentheses

 

 

괄호가 제대로 구성되어 있는지 파악하는 문제다.

제대로 구성됐다는 것은 닫는 괄호가 나올 때 제일 최근에 있는 여는 괄호와 매칭된 형태이다.

여는 괄호를 스택에 넣고

닫는 괄호가 나올 때 스택에 있던 값을 pop 하여 

괄호가 매칭되는지 확인한다.

 

괄호가 매칭되지 않는 경우는

• 1) 닫는 괄호가 여는 괄호가 매칭되지 않거나 "(]"
• 2) 닫는 괄호는 있지만 여는 괄호가 없거나 "()]"
• 3) 여는 괄호가 덩그러니 남아있거나 "(()"

class Solution:
    def isValid(self, s: str) -> bool:
        
        temp = []
        match = {'{':'}', '[':']', '(':')'}
        
        # 시간복잡도 O(N) : 하나씩 쭈욱 탐색 O(N) + pop 시간복잡도는 O(1)
        # 공간복잡도 O(N)
        
        for i in s:
            if i=='{' or i=='[' or i =='(': # 여는 괄호 (스택에 쌓음)
                temp.append(i)
            else: # 닫는 괄호
                if i != match[temp.pop()]: # 1) 괄호가 매칭 안되는 경우
                    return False
                if not temp : return False # 2) 여는 괄호가 이전에 없었던 경우
        if temp : return False # 3) 여는 괄호만 남아있는 경우
        
        return True
                    
                
        

 

복잡도는 최악의 경우로 생각한다.

 

시간복잡도 O(N)

• 하나씩 쭈욱 탐색 O(N) + pop 시간복잡도는 O(1)

공간복잡도 O(N)

• 최악의 경우 길이가 N인 추가 공간 (temp 배열) 필요함.
• 입력이 "((((" 이렇게 주어질 때 temp의 길이는 N임.