[자료구조] 대중소 괄호 짝 맞추기 파이썬 (stack, valid parentheses)

stack의 대표적 문제니까 다시 또 체크

 

3.28일에 풀었네 (link)

 

이건 물론 다른 사람의 풀이

def solution(s):
    stack = []

    # Hash map for keeping track of mappings. This keeps the code very clean.
    # Also makes adding more types of parenthesis easier
    mapping = {")": "(", "}": "{", "]": "["}

    # For every bracket in the expression.
    for char in s:

        # If the character is an closing bracket
        if char in mapping:

            # Pop the topmost element from the stack, if it is non empty
            # Otherwise assign a dummy value of '#' to the top_element variable
            top_element = stack.pop() if stack else '#'

            # The mapping for the opening bracket in our hash and the top
            # element of the stack don't match, return False
            if mapping[char] != top_element:
                return False
        else:
            # We have an opening bracket, simply push it onto the stack.
            stack.append(char)

    # In the end, if the stack is empty, then we have a valid expression.
    # The stack won't be empty for cases like ((()
    return not stack

이 풀이에서 중요하게 보는 점은 3번째 if 문이다.

 

if char in mapping의 조건에서(close parenthesis를 찾았다면)

pop한 element(top_element)와 close parenthesis의 key인 open parenthesis가 다르면

바로 return해버리면서

나머지 loop를 돌지 않아도 된다는 점이다.

 

또한, if stack else "#" 을 넣어줘서 safety device 역할을 해준 것 같다.

---

내 풀이

class Solution:
    def isValid(self, s: str) -> bool:
        # s = "{[]}"
        # s = "{[]}"
        stack = []
        # stack.append(s[0])
        for c in s:
            if len(stack) == 0: # 최초에 stack이 비었더라도 loop진행중 stack이 비워지면 다시 채워넣기
                stack.append(c)
            elif stack[-1] == "{" and c == "}":
                
                stack.pop()
            elif stack[-1] == "[" and c == "]":
                
                stack.pop()
            elif stack[-1] == "(" and c == ")":

                stack.pop()
            else:
                stack.append(c)
        print(stack)
        if len(stack) == 0:
            return True
        else:
            return False