종류는 '(', ')', '[', ']', '{', '}' 으로 총 6개 있습니다.
아래의 경우 유효합니다.
한 번 괄호를 시작했으면, 같은 괄호로 끝내야 한다.
괄호 순서가 맞아야 한다.
예를 들어 아래와 같습니다.
s = "()"
return true
s = "()[]{}"
return true
s = "(]"
return false
def is_valid(string):
stack= []
dict = {"(": ")", "{": "}", "[": "]"}
if len(string) == 1:
return False
for i in string:
if i in dict:
stack.append(i)
elif len(stack) == 0 or dict[stack.pop()] != i:
return False
return len(stack) == 0
stack
을 생성한다. 여기에 for문으로 체크한 string의 요소가 들어 갈 것이다.dict
에 괄호를 종류별로 저장한다. 이 때, key에는 열림괄호, value에는 닫힘괄호를 저장한다.dict
에 있는지를 확인한다 (딕셔너리이므로 key값에 있는지가 확인된다.)stack
에 해당 요소를 더해준다.stack.pop
은 마지막 요소를 지우고 불러온다. 따라서 dict[stack.pop()]
은, 현재 요소가 stack에 저장된 열림괄호에 해당하는 value인지를 체크한다.stack.pop
이 실행되어, stack에서 요소가 제거되기 때문에, 최종 string의 길이는 0이어여만 유효하다.def is_valid(string):
left = ['(', '{', '[']
right = [')', '}', ']']
stack = []
for letter in string:
if letter in left:
stack.append(letter)
elif letter in right:
if len(stack) <= 0:
return False
if left.index(stack.pop()) != right.index(letter):
return False
return len(stack) == 0