[스택, 큐] 20 유효한 괄호(Valid Parentheses)

<LeetCode 문제>

https://leetcode.com/problems/valid-parentheses/

Valid Parentheses - LeetCode

괄호로 된 입력값이 올바른지 판별하는 문제입니다.

<풀이>

전형적인 스택 문제입니다. (,{,[에서는 스택에 push하고 ),},]에서는 스택에서 pop한 결과가 mapping되는지 확인합니다.

이를 위해서 매핑 테이블을 미리 만들어줘야 합니다.

그리고 pop할때 스택이 비어있으면 안되므로 비어있는 상황에 대한 예외처리도 해주어야 합니다.

 

첫번째 풀이에서 적은 코드는 다음과 같습니다.

#처음 푼 풀이
class Solution:
    def isValid(self, s: str) -> bool:
        stack =[] #스택으로 사용
        match ={')':'(','}':'{',']':'[' }
        
        for now_char in s:
            if now_char in {'(', '{','['}:
                stack.append(now_char) #스택에 push
            else:
                if not stack or stack.pop() != match[now_char]:
                    return False
        
        if stack: #다 끝났는데 스택이 차있는경우
            return False
        else:
            return True

 

이후에 코드를 리팩토링한 결과는 다음과 같습니다.

#다듬어진 풀이
class Solution:
    def isValid(self, s: str) -> bool:
        stack =[]
        match ={')':'(','}':'{',']':'[' }
        
        for now_char in s:
            if now_char in match: #matching 테이블 이용하면 됨
                stack.append(now_char)
            elif not stack or stack.pop() != match[now_char]: #else안에 if 하나 elif로 정리
                    return False
        
        return len(stack)==0 #스택이 비어있는걸 len으로 확인

 

<학습내용>

1. 딕셔너리를 for문으로 돌때 key값들이 순서대로 참조됩니다.
2. 빈 리스트를 확인할때 len()값이 0인지 확인해서 합니다.

<학습이 필요한 내용>

1. X