LeetCode [20]: Valid Parentheses

📌 LeetCode [20]: Valid Parentheses

🔗 문제 링크

---

문제 설명 📄

여러 종류의 괄호((), {}, [])로 이루어진 문자열 s가 주어질 때, 문자열이 올바른 괄호 문자열인지 판단하는 문제입니다.
올바른 괄호 문자열의 조건:

1. 괄호는 반드시 짝을 이루어야 한다.
2. 괄호는 열리고 닫히는 순서가 올바르다.

---

문제 접근 방식 📋

1. 스택 활용:
   • 여는 괄호((, {, [): 스택에 추가.
   • 닫는 괄호(), }, ]): 스택에서 가장 최근의 여는 괄호를 꺼내서 짝이 맞는지 확인.
2. 조건 검증:
   • 닫는 괄호가 나왔을 때 스택이 비어 있으면 짝이 맞지 않으므로 False.
   • 모든 괄호를 처리한 후, 스택에 남아 있는 여는 괄호가 있으면 False.
3. 최종 결과:
   • 문자열을 끝까지 처리했을 때 스택이 비어 있으면 올바른 괄호 문자열.

---

Solution 💻

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

        return not stack  

시간 복잡도 분석 ⏲️

• 시간 복잡도: (O(n))
  • 문자열의 각 문자를 한 번씩 처리.
• 공간 복잡도: (O(n))
  • 최악의 경우(모두 여는 괄호): 스택에 모든 문자가 저장됨.

---