[LeetCode] Algorithms | 20. Valid Parentheses | Python

Problems

 

문제를 읽고, 그냥 순서 상관없이 s안에 짝 맞는 괄호만 있으면 되는 줄 알았다.

그래서 짠 코드는 아래와 같다.

진짜 단지 짝만 맞으면 되기에, 같은 괄호 짝수 개인지 확인하고 return

wrong 이라고 한다.

보니까, 같은 괄호끼리는 붙어있어야하나보다.

 

만약 s = '( [ { } ] )' 일 경우에는 여는 괄호 순서  ( → [ → {  와 닫는 괄호  } → ] → ) 순서는 반대이다.

이런 경우에 여는 괄호 순서로 stack에 쌓아주고, 뒤에 쌓인 순서대로 가지고 와서 닫는 괄호 확인하는 걸로 해야겠다.

그럼 LIFO 가 되는거고, list에서 뒤에 요소부터 가지고 와서 지워주는 pop 을 사용해야겠다

(remove는 앞 요소를 가지고 오고 지워준다.)

 

그래서 작성한 스크립트는 아래와 같다.

class Solution:
    def isValid(self, s: str) -> bool:

        stack = []
        bracket_pairs = {'(':')', '[':']', '{':'}'}

        if len(s)%2 == 1: # 짝 맞는 지 확인
            return False

        for char in s:
            if char in bracket_pairs.keys(): # 여는 괄호이면 stack에 쌓기
                stack.append(char)
            elif not stack: # 닫는 괄호로 시작 하면 False
                return False
            elif bracket_pairs[stack.pop()] != char: # 괄호 짝이 안맞으면 False
                return False
		
        # s="((" 같이 여는 괄호만 있는 경우에 stack에 남아있게 된다.
        # 이런 경우를 대비하기 위해서 stack에 남아있는기 검사한다.
        return len(stack) == 0

 

성공