[LeetCode] 20. Valid_Parentheses (Easy) 2023/5/8

문제 제목	정답률	난이도
20. Valid_Parentheses	40.5%	Easy

Valid Parentheses - LeetCode

 

문제요약

문자열이 주어질 때, 입력값이 올바른지 판단하라

조건 1) 문자열은 소괄호 (), 중괄호 {}, 대괄호 []로 구성되어 있다

조건 2) 열린 괄호들은 같은 종류의 닫힌 괄호와 올바른 순서로 매칭되어야 한다.

조건 3) 문자열의 길이는 1 이상이고, 반환값으로 참이나 거짓을 가져야 한다

 

 

풀이 1

스택을 이용

Step1. 열린괄호, 닫힌괄호 매치 여부를 판단하기 위해 딕셔너리 이용

 

Step2. 문자열의 문자에 대해 판단

• 열린 괄호이면 스택에 삽입
• 닫힌 괄호이면 바로 스택.top이랑 매치되는지 확인
  • 스택 길이가 0이거나, 매치되지 않으면 거짓 반환

 

Step3. return 값 최적화

• 스택길이가 0이여야 참 값을 반환, 그렇지 않다면 거짓을 반환하는데
• 이때, if 구문을 이용하는 것보다, return에서 바로 판단하여 반환하는 게 약 10ms 가량 시간 절약

 

 

구현 (43ms)

class Solution:
    def isValid(self, s: str) -> bool:
        stack=[]
        parentheses_dict={'(':')', '{':'}', '[':']'}
        for char in s:
            if char in ['(', '{', '[']:
                stack.append(char)
            elif len(stack)==0 or parentheses_dict[stack.pop()]!=char:
                return False
            else:
                continue
        return len(stack)==0