Valid Parentheses - leetcode(316)

Valid Parentheses

요구사항

• Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
• Open brackets must be closed by the same type of brackets.
• Open brackets must be closed in the correct order.
  => (), [], {}만 포함하는 문자열 s가 주어진다면 입력문자열이 유효한지 확인한다.
  => 열린 괄호는 동일한 유형의 괄호로 닫혀야하고, 열린 괄호는 올바른 순서로 닫혀야한다.

Solution

preInput = "{()}"

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        
        opener = "{[("
        
        # Stack에 여는 괄호를 넣기 때문에 닫는 괄호가 들어 왔을때 stack의 top과 비교하기
        # 때문에 key를 닫는괄호로 넣고, val을 여는 괄호로 넣어서 동일한지 비교하게 된다.
        pair = {
            "}": "{",
            "]": "[",
            ")": "("
        }

        for char in s:
            if char in opener:
                stack.append(char)
            else:
                if not stack:
                    return False
                # stack의 top위치의 여는 괄호를 가져와서 닫는 괄호와 key의 value와 비교하는 것이다.
                top = stack.pop()
                if pair[char] != top:
                    return False
                
        return not stack
        
sol = Solution()

print(sol.isValid(preInput))
# >>> True

📌 코드 풀이

1. "{", "[", "(" 등 오픈 괄호가 쌓일 stack을 선언해준다.
2. opener = "{[(" 를 선언하여 include로 이용할 수 있게 만들어준다.
3. opener가 아닐 경우 비교를할 예정이기 때문에 괄호로 만들어진 dictionary를 만드는데 key는 닫는괄호 value는 여는괄호를 넣어서 만들어준다.
   => 스택에 여는 괄호를 넣기 때문에 닫는괄호가 들어오면 stack의 top과 비교하는 것이다.
4. 입력값을 for문을 돌려서 철자 하나 하나를 가져오고, if문으로 opener라면 스택에 넣어준다.
5. opener가 아닌 경우, stack이 비었다면 바로 False이고 stack.pop()으로 마지막에 쌓인 괄호를 가져온 뒤 pair[char] != top 로 서로 짝이 맞지 않다면 False를 반환한다.
6. for문이 정상적으로 끝난경우, 검증은 끝났기 때문에 return not stack으로 stack이 비었다면 짝을 다 찾아서 나갔기 때문에 True를 아니라면 False를 반환한다.

leetcode

https://leetcode.com/problems/remove-duplicate-letters/