[Leetcode] 20. Valid Parentheses

문제

 

https://leetcode.com/problems/valid-parentheses/

Valid Parentheses - LeetCode

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.

(),{},[]로 이루어진 문자열이 주어졌을 때 해당 문자열이 유효한지 확인해라.

    1. 열린 괄호와 닫힌 괄호는 같은 유형의 괄호여야한다.

    2. 열린 괄호는 올바른 순서대로 닫아야한다.

    3. 모든 닫힌 괄호는 같은 유형의 열린 괄호가 존재한다.

 

문제풀이 코드

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

 

 

풀이방법: stack

1. 주어진 문자열을 리스트로 변경

2. stack 초기화 -> 비교를 위해 리스트의 첫번째 인자를 stack에 담아준다

3. s에 값이 존재할 때 stack이 비어있으면 stack에 값 추가

4. s에 값이 존재하지 않으면 False를 리턴 

5. stack에 들어있는 마지막 값과 리스트s의 첫번째 값이 상응하는 괄호이면 stack과 s에서 제거

6.stack에 값이 존재하면 일치하지 않는 괄호가 존재함으로 False를 리턴

7. 리스트s가 존재하지 않을때까지 반복