📕문제

LeetCode 20. Valid Parentheses

문제 설명

괄호들로 이루어진 문자열이 유효한지 확인하는 문제다.

조건

1. 열린 괄호는 같은 유형의 괄호로 닫아야 한다.
2. 열린 괄호는 올바른 순서대로 닫혀야 한다. (=열린 순서가 늦은 순서대로 닫혀야 한다.)
3. 모든 괄호는 쌍을 이루어야 한다.

---

📝풀이

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        parentheses = ['(', '{', '[', ')', '}', ']']
        for i in s:
            if parentheses.index(i) < 3:
                stack.append(parentheses.index(i))
            else:
                if not stack or stack.pop()+3 != parentheses.index(i):
                    return False
        return False if stack else True

• 문자열의 다음 괄호가 열림 괄호인 경우 stack 에 추가한다.
• 닫힘 괄호인 경우 스택이 비어있는지(= 열림 괄호 없이 닫힘 괄호가 출현),
  스택에서 꺼낸 괄호와 쌍을 이루는지 검사
• 문자열을 모두 순회 후 stack이 비어져 있다면 True, 그렇지 않으면 Flase.

---

문제를 풀고 다른 풀이들을 보니 딕셔너리를 이용해 괄호들을 짝지은 경우가 많았다.
주어진 쌍이 해당 문제와 달리 단순하지 않은 경우 위의 코드가 좋지 않겠다는 생각이 들어 이를 참고해 개선해보았다.

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        parentheses = {
            '(': ')',
            '{': '}',
            '[': ']'
        }
        for i in s:
            if i in parentheses:
                stack.append(parentheses[i])
            else:
                if not stack or stack.pop() != i:
                    return False
        return False if stack else True

• 열림 괄호가 key, 닫힘 괄호가 value인 딕셔너리를 만든 후 이를 활용했다.