[스택, 큐] 유효한 괄호

 

20 | Valid Parentheses
https://leetcode.com/problems/valid-parentheses/

 

 

 

작성 코드

 

class Solution:
    def isValid(self, s: str) -> bool:
        s = list(s)
        stack = []
        parenthneses = {'{': '}', '(': ')', '[': ']'}
        while s:
            stack.append(s.pop())
            while len(stack) >= 2 and stack[-1] in parenthneses and stack[-2] == parenthneses[stack[-1]]:
                stack.pop()
                stack.pop()
        return False if stack else True

 

• list에 있는 문자를 stack에 하나씩 append
• stack 길이가 2 이상이고, stack의 마지막 원소가 parenthneses의 key값으으로 존재하고, stack[-2] 값이 stack[-1] 를 key 값으로 갖는 value와 같을 때 pop 해줌
• '{[]}' -> '}][{'

 

s	stack
{[]}	}
{[	}]
{	}][
	}{

 

 

 

이상 코드

 

class Solution():
        def isValid(self, s:str) -> bool:
            stack = []
            table = {
                ')': '(',
                '}': '{',
                ']': '['
            }


            for char in s:
                if char not in table:
                    stack.append(char)
                elif not stack or table[char] != stack.pop():
                    return False
            return len(stack) == 0

 

• s 앞부터 문자 가져옴
• 여는 괄호(table key 가 아님)면 stack에 append
• 닫는 괄호인데, stack이 비어있거나 stack의 마지막 원소가 쌍이 아니라면 유효하지 않음 -> 바로 False return 

 

 

학습

 

• dictionary 자료형을 유용하게 사용하자
• 조건문을 깔끔하게