03/18 알고리즘 문제풀이 - 20. Valid Parentheses

문제

• Leetcode 알고리즘 문제
• 20. Valid Parentheses
• 문제 내용 : [링크]
  

내가 작성한 코드

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        for e in s:
            if e == '(':
                stack.append(')')
            elif e == '[':
                stack.append(']')
            elif e == '{':
                stack.append('}')
            elif stack and stack[-1] == e:
                stack.pop()
            else:
                return False
        return not stack

• 짝을 맞추는 형식의 전형적인 stack 예제 문제이다. 문자열 s의 글자를 탐색하면서, '(', '[', '{'가 나오면 올바른 사용이 되었는 지 True / False를 출력한다.

• stack 리스트를 만들어주고 문자열 s의 완전탐색을 한다. 만약 해당 문자가 '(', '[', '{' 라면, stack에 ')', ']', '}'
  를 추가해준다.

• 탐색 중, 문자가 ')', ']', '}' 라면, stack에서 pop() 해준다. 항상 스택은 가장 마지막에 추가된 자료가 중요(stack[-1])

• 위의 모두에 해당되지 않을 경우, False출력 해준다. (stack[-1]이 이전에 열린 괄호를 닫을 수 없다는 뜻임)

• not stack 을 return하여 stack에 원소가 남아있으면 False, 없으면 True를 출력한다.

⭐

1. 왜 stack 사용? - 괄호는 안쪽의 괄호를 닫고 바깥쪽 괄호를 나중에 닫는다. 즉 Last In, First Out 방식으로 작성되어야 한다. 따라서 stack을 사용했다.

2. 짝을 찾거나 묶음이 제대로 만들어졌는 지 확인하는 문제는 대부분 stack으로 해결할 수 있다.