[LeetCode]Valid Parentheses

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

Valid Parentheses - LeetCode

 

문제 분석

괄호의 쌍이 정상적으로 존재하는지 체크하는 문제입니다. 일명, VPS 알고리즘 입니다.

 

처음 시도한 답안

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

        for char_ in s:
            if char_ == '(':
                stack.append(char_)
            if char_ == '{':
                stack.append(char_)
            if char_ == '[':
                stack.append(char_)
            
            if char_ == ')':
                if not stack or stack.pop() != '(':
                    return False
            if char_ == '}':
                if not stack or stack.pop() != '{':
                    return False
            if char_ == ']':
                if not stack or stack.pop() != '[':
                    return False

        if stack:
            return False

        return True

접근 방법

1. 스택 구조를 활용합니다.
2. 열려있는 괄호라면 스택에 순서대로 넣습니다.
3. 닫혀있는 괄호를 만날경우 스택에서 pop 했을 때 맞는 쌍이 아닌 경우 False를 돌려줍니다.
4. 반복을 순회한 후에도 스택에 값이 남아 있다면 모두 열고 닫힌 것이 아니므로 False를 리턴합니다.
5. 반복을 순회한 후에 스택에 값이 없다면 True를 리턴합니다.

열려 있는 모양의 괄호들만 스택에 넣어서 닫혀 있는 모양의 괄호를 만날때 하나씩 pop 하면서 쌍을 이루는지 확인하는 것이 포인트 입니다.

스택 구조를 활용하면서 발생할 수 있는 모든 케이스를 if문으로 분기처리해 구현 했습니다. 다만 코드가 조금 지저분해지는 경향이 있어 최적화를 해보았습니다.

 

두번째로 시도한 답안

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

        stack = []
        for char_ in s:
            if char_ in left_chars:
                stack.append(char_)
            
            if char_ in right_chars_dict:
                if not stack or stack.pop() != right_chars_dict[char_]:
                    return False

        if not stack:
            return True
 
        return False

접근 방법

접근 방법은 첫번째와 동일합니다. 다만 딕셔너리와 리스트 구조를 활용해서 반복되는 if문을 하나로 통일할 수 있었습니다.

실전이라면 처음부터 이렇게 풀이하는 것은 조금 어려울 것 같고, 우선 문제를 푼 뒤에 최적화 하는 방법을 택할 것 같습니다.