[LeetCode 해석 및 풀이] 20. Valid Parentheses

LeetCode 문제 해석 및 풀이 방법

 

문제 20. Valid Parentheses(유효한 괄호)

바로가기

 

문제 설명

영문

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

 

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
3. Every close bracket has a corresponding open bracket of the same type.

 

한글

문자 (,),{,},[,] 만으로 이루어진 문자열 s가 주어질 때, 해당 입력이 유효한지 결정하세요.

 

이럴 경우 입력 문자열은 유효합니다:

1. 열린 괄호는 반드시 같은 타입의 괄호로 닫혀야 합니다.
2. 열린 괄호는 반드시 맞는 순서로 닫혀야 합니다.
3. 모든 닫힌 괄호들은 동일한 유형의 열린 괄호가 있어야 합니다.

 

제한조건

• 1 <= s.length <= 104
• s consists of parentheses only '()[]{}'.

 

입출력 예

입력	출력
s = "()"	true
s = "()[]{}"	true
s = "(]"	false

 

 

해답 및 해설

파이썬 (Python)

neetcode 로드맵에 나온대로 대표적인 stack을 이용한 문제.

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

        for c in s:
            if c in pair:
                stack.append(c)
            else:
                if len(stack) == 0: return False
                o = stack.pop()
                if pair[o] != c: return False
        
        if len(stack) != 0: return False
        return True

마지막에 열린 괄호는 맨 처음에 닫혀야 하므로 stack을 이용한다. 우선 열린 괄호일 때는 스택에 넣는다. 닫힌 괄호일 때는 스택에서 빼는데, 스택이 비어있지 않은지, 빠진 열린 괄호가 닫힌 괄호와 타입이 같은지 체크해준다. 마지막에 스택이 비어있는지 확인해주고 모두 정상이면 True, 중간 과정 중 하나라도 오류가 있다면 False를 반환해준다.