Valid Parentheses

Valid Parentheses - LeetCode

접근 방법 [필수 작성]

제한 조건 확인

• 최대 O(n^2) 알고리즘을 사용할 수 있음
• 괄호 종류 3개밖에 없기 때문에 룰베이스 조건문 작성 가능

아이디어

stack 활용

괄호가 열릴때마다 짝이 맞는 닫히는 괄호를 스택에 저장

열리는 괄호에 해당되지 않을때 스택에서 한개를 pop 해서 짝이 맞는지 확인

어느경우에도 해당되지 않으면, 짝이 맞지 않거나, 이미 모든 s 순회했는데, 스택에 괄호가 남아있는 경우임

시간복잡도

O(n)

자료구조

코드 구현 [필수 작성]

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

        for i in range(len(s)):
            if s[i] == "(":
                stack.append(")")
            elif s[i] == "[":
                stack.append("]")
            elif s[i] == "{":
                stack.append("}")
            elif stack and stack.pop() == s[i]:
                pass
            else:
                return False
        
        if stack:
            return False

        return True

배우게 된 점 [ 필수 X ]

첫 제출 때 for 문을 다 돌았을때, stack 에 남아있는 경우인

s = “{{{{{” 인 경우를 생각못해서 만점을 못받았다.

        if stack:
            return False

위 코드를 추가하여 해결하였다.

질문 [ 필수 X ]

자유 형식

피드백 [ 코치 작성 ]

수고하셨습니다!