20. Valid Parentheses

🚥 문제 🚥

Top Interview 150 중
20. Valid Parentheses!

🍿 난이도 : 리트코드 기준 Easy

🚦 풀이1 🚦

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        for i in s:
            if (i == "(" or i == "{" or i == "[") : 
                stack.append(i)
                continue
            if (len(stack) and i == ")" and stack[-1] == "("):
                stack.pop()
                continue
            if (len(stack) and i == "}" and stack[-1] == "{"):
                stack.pop()
                continue
            if (len(stack) and i == "]" and stack[-1] == "["):
                stack.pop()
                continue
            stack.append(i)
        if (len(stack)):
            return False
        return True

🚧 알고리즘 : 구현

🚧 stack구현을 위해서 python의 list 자료구조를 사용했다.
🚧 여는괄호인 (, {, [일경우 stack에 추가해주고, 닫는 괄호일경우 stack에 마지막으로 들어간 괄호와 비교해서 삭제해주거나, 맞지 않을 경우 stack에 추가해주었다.
🚧 마지막에 stack의 길이를 체크해서 만약 stack에 남은 값이 있을 경우 false를, stack이 비었을 경우 true를 리턴해주었다.

풀이 결과

🚦 풀이2 🚦

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        check = dict({'()','{}','[]'})
        for i in s:
            if i in '({[' :
                stack.append(i)
                continue
            if not stack: #empty list is fals in if not :
                return False
            if (i == check[stack[-1]]):
                stack.pop()
                continue
            else : 
                return False
        return not stack

🚧 알고리즘 : 구현

🚧 위의 풀이와 비슷하게 stack을 사용했지만 추가로 python의 dict 구조도 사용했다.

🚧 dict({'()','{}','[]'}) 의 결과가
{'(': ')', '[': ']', '{': '}'} 이렇게 생긴 dictionary를 만든다는 것을 처음 알았다.
딱 2글자의 string들로 이루어진 tuple에 대해서만 변환이 된다.

🚧 if문들이 체크하는 공통적인 조건인 stack에 남은 값이 있는지 없는지를 빼서 하나의 조건문으로 만들었다. if not stack: 이 조건문은 list에 대해서 체크하는데, list가 비어있을 경우 True가 되어 최종적으로 함수에서 False를 리턴한다.

풀이 결과

런타임에서 10%정도 개선되었지만 보다 메모리 사용량에서 상당부분 사용했음을 알 수 있다. 아무래도 자료구조를 1개의 리스트만 사용하던 1번 풀이법보다 2번 풀이법이 자료구조 개수가 증가해 더 많은 메모리를 사용한 것 같다.