[LeetCode] 20. Valid Parentheses 유효한 괄호

파이썬으로 배우는 알고리즘 책을 공부하며 풀었던 LeetCode문제들을 재정리해보자.

 

# 문제 설명 

20번 Valid Parentheses는 입력된 괄호 쌍들이 순서에 맞게 잘 닫혀있는지 확인하는 문제이다. 

Example

 

 

# 풀이방법 1 -  재귀 함수 이용하여 reverse (내 풀이)

class Solution:
    def isValid(self, s: str) -> bool:
    
        checkStack = []
        brackets = { '(' : ')', '{' : '}' , '[' : ']' } # bracket 쌍 보관
        
        for c in s :
            if c in list(brackets.keys()):
                checkStack.append(c) # 시작 브라켓은 스택에 저장 
            else :    
                if checkStack : 
                	# 맞지 않은 브라켓으로 닫히면 안 됨 
                    if brackets[checkStack.pop()] != c :  
                        return False
                        
                else : # 닫힌 브라켓이 먼저 시작되면 안 됨
                    return False
                
       
        # bracket이 안 닫힌 경우
        if checkStack :
            return False
        else :
            return True

| 아이디어  | 

기본 아이디어는 시작 괄호를 스택에 저장하고, 닫는 괄호가 있을 경우세는 스택에서 pop하여 마지막 시작 괄호의 쌍이 맞는지 확인한다. 

1. 시작 브라켓은 스택에 저장하고, 만약 닫힌 브라켓이 먼저 오면 return False

2. 닫힌 브라켓의 경우, 스택에서 pop하여 마지막 시작 브라켓의 쌍인지 비교하여 아니라면 return False

3. 만약 브라켓이 닫히지 않고 끝난다면 stack에 저장되어 있을테니, 스택 checkStack가 비어있는지 확인하고 그에 따라 결과값을 return 한다.  

 

 

 

# 풀이 방법 2 - 아직 안 봄 (책 풀이 참고)

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

| 아이디어 | 

책의 풀이는 먼저 매핑 테이블을 만들어 놓고 테이블에 존재하지 않으면 무조건 푸시하고, 팝 했을 때 결과가 일치하지 않으면 False를 return 한다.  

 

 

 

# 결과 

결과

(책의 풀이는 leetcode에 풀지 않은 상태)