•
•
문제 설명 : 괄호로 구성된 문자열이 정상적인 괄호쌍이 맞는 문자열인지 여부를 반환
•
풀이 방법
◦
괄호 문제는 대부분 Stack으로 많이 해결한다.
▪
이유는 정상적인 쌍으로 구성된 문자열이라면, 가장 마지막에 추가된 열린 괄호가 가장 처음 확인되는 닫힌 괄호와 무조건 매칭되기 때문이다.
▪
이것을 사용해서, 열린 괄호는 스택에 추가하고 닫힌 괄호를 확인한다면 스택에서 제외하는 방식으로 진행한다.
•
시간복잡도 :
•
성공 코드
class Solution:
def isValid(self, s: str) -> bool:
stack = []
open_parenthesis = {
'(': ')',
'{': '}',
'[': ']',
}
close_parenthesis = {
')': '(',
'}': '{',
']': '['
}
for ch in s:
# 열린 괄호는 스택에 추가
if ch in open_parenthesis:
stack.append(ch)
# 닫힌 괄호일 때
elif ch in close_parenthesis:
# 만약 열린 괄호가 존재하지 않거나, 가장 마지막에 추가된 열린괄호가 쌍이 안맞는 경우 유효하지 않은 문자열로 처리
if not stack or stack.pop() != close_parenthesis[ch]:
return False
return len(stack) == 0
Python
복사