https://leetcode.com/problems/valid-parentheses/
문제 파악
'(', ')', '{', '}', '[' ,']' 가 들어오고 괄호가 짝이 맞게 닫히게 되어야 한다. 여는 괄호가 먼저 들어와야 하고 닫히는 괄호도 순서에 맞게 닫혀야한다.
접근 방법
stack처럼 LIFO 형태를 띄게해서 먼저 들어온게 늦게 빠져나가게 생각해야 한다. 각자의 짝에 맞는 괄호를 새로운 리스트에 넣고 그 리스트를 스택으로 구성한다. 그렇게 된다면 문자열의 닫을 때가 스택의 가장 마지막 요소와 같다면 올바르게 된 것이고 이를 통해 True, False를 판별할 수 있게 된다.
예를 들어, 문자열 "{([]})" 을 살펴보자. 앞에서 열린 괄호 '{' , '(' , '['가 연속적으로 3개가 나열된다. 그러면 유효한 문자열이 되기 위해서는 ']' , ')' , '}' 가 순서대로 나열되어야한다. ']' 은 '[' 과 대응되기 때문에 유효하다. 따라서 스택에서 '[' 은 제거한다. 따라서 유효성을 유지하기 위해 예상되는 다음 닫힌 괄호는 ')' 이다. 왜냐하면 현재 가장 최근에 추가된 열린 괄호는 '(' 이기 때문이다. 하지만 '}' 이 주어지기 때문에, 유효성 조건을 위반한다. 그래서 문자열 "{([]})" 은 유효하지 않다고 판단할 수 있다.
코드 구현
class Solution:
def isValid(self, s: str) -> bool:
# 기본 값 세팅
stack = []
# 문자열 s를 문자 단위로 순회
for p in s:
# 열린 괄호에 따라 대응되는 닫힌 괄호 추가
if p == "{":
stack.append("}")
elif p == "[":
stack.append("]")
elif p == "(":
stack.append(")")
# 현재 문자가 닫힌 괄호 일때, 스택의 마지막 문자가 현재 문자와 같다면, pop!
elif stack and stack[-1] == p:
stack.pop()
else:
return False
# 순회를 종료하고 stack이 비어있다면 True, 아니라면 False
return not stack배우게 된 점
처음 문제를 접했을 때 새로운 스택을 만들어서 처리하는 생각은 못했는데 생각을 확장한 것 같다.
++ 0710
다시 풀어보면서 생긴 의문점
elif stack and stack[-1] == p 가 아닌 x == stack[-1]으로만 코드를 작성하면 왜 인덱스 초과 오류가 발생하나요?
++ 0711
return not stack → stack이 비어있다면 true를 반환하겠죵
질문
++ 0710
elif stack and stack[-1] == p 가 아닌 x == stack[-1]으로만 코드를 작성하면 왜 인덱스 초과 오류가 발생하나요? 왜 stack을 적어야 하는지 잘 모르겠습니다.
만약에.. 스택이 비어있다면 어떻게 될까요?
stack = [] 이런 상태인 겁니다.
근데 제일 뒤에있는 원소에 접근하려고 한다?
아무것도 없는 곳에서 찾으려고 하니까 문제가 발생하겠죠?
elif stack and stack[-1] == p
이 코드에서 stack이라고 적혀있는 부분의 의미가 이제 중요합니다.
참 거짓을 판별할 때 리스트 객체를 판별 조건으로 작성하면 빈 리스트일 때 False를 그렇지 않은 경우에는 True를 반환합니다.
따라서 elif stack 부분도 비어있는지 확인을 한 후 비어있다면 False가 되므로 stack[-1] == p 이 부분은 확인하지 않고 조건문을 탈출하게 됩니다. 따라서 예외가 발생하지 않겠죠?
