You Nicholas

가고 가고 또 가면 알게되고, 행하고 행하고 또 행하게 되면 이루게 된다.

최대 1 분 소요

1. 문제Permalink

20. Valid Parentheses

Easy

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

  1. Open brackets must be closed by the same type of brackets.
  2. Open brackets must be closed in the correct order.

 

Example 1:

Input: s = "()"
Output: true

Example 2:

Input: s = "()[]{}"
Output: true

Example 3:

Input: s = "(]"
Output: false

 

Constraints:

  • 1 <= s.length <= 104
  • s consists of parentheses only '()[]{}'.

출처: Leetcode, https://leetcode.com/

2. 해결방법 시간복잡도Permalink

  1. 스택 O(N)

3. 문제 해결 및 코드Permalink

class Solution:
def isValid(self, s: str) -> bool:
stack = [] # 스택으로 해결
tmp = {")":"(",
"]":"[",
"}":"{"}
# 괄호 열고 닫고 정보 저장
for i in s:
if i in tmp.values(): # 만약 괄호가 열리는 경우
stack.append(i)
else:
if stack and tmp[i] == stack[-1]:
# 현재 스택이 존재하고 쌓여있으면서 괄호가 닫히는 경우
stack.pop()
else:
# 닫을 괄호가 스택에 없거나 열린 괄호랑 다를 경우
return False
if stack: return False
else: return True
view raw 20.py hosted with ❤ by GitHub

  • 주석을 참고하면서 이해를 돕습니다.Permalink

4. 알고리즘 및 해설Permalink

  1. 스택과 딕셔너리를 통해 문제를 해결하였다.
    • 괄호문제들은 보통은 대게 스택으로 간단하게 풀이가 가능하다.
  2. 반복문을 통해 해당 값이 괄호를 여는 경우라면 스택에 넣는다.
    • 이때 괄호가 닫히는 문구가 열린 문구와 쌍을 이룬다면 스택에서 빼준다.
  3. 최종적으로 스택안에 뭔가가 존재한다면(괄호가 열려있거나 하나 더 닫혀있거나) False를 반환하고 아니라면 True를 반환한다.

참고