“파이썬 알고리즘 인터뷰” + https://leetcode.com/problems/valid-parentheses/
스택과 큐 파트로 넘어왔다. 학부에서 가장 처음 배우는 자료구조가 스택과 큐가 아닌가 한다. 기본이고 단순한 구조이지만 실제 사용하지 않으면 모르는 건 매한가지다.
첫 문제는 주어진 괄호들이 올바른지 판별하는 것이다. 괄호가 올바르게 닫혔는지를 보면 된다. “()[]”과 “[{()}]”는 True이고 “[)”나 “[{}(])”는 False이다.
def isValid1(self, s: str) -> bool:
stack = []
table = {
"(": ")",
"[": "]",
"{": "}"
}
for chr in s:
if table.get(chr):
stack.append(chr)
else:
if not stack or table.get(stack.pop()) != chr:
return False
if stack:
return False
return True
def isValid2(self, s: str) -> bool:
stack = []
table = {
")": "(",
"]": "[",
"}": "{"
}
for char in s:
if char not in table:
stack.append(char)
elif not stack or table[char] != stack.pop():
return False
return len(stack) == 0
isValid1이 내 풀이인데 책에서와 비슷하게 됐지만 괄호를 정의하는 딕셔너리 변수 “table”을 반대로 정의했더니 조건문이 꼬여서 바로 풀리지 않았다. 그리고 leetcode에서 예외적인 입력으로 “[“나 “]”와 같은 것들이 있어서 내 소스는 조금 지저분하게 돼버렸다.