문제 링크
문제 요약
Lesson 7의 Stacks and Queues 에 해당한다.주어진 문자열에서 "()" , "[]" , "{}"로 잘 중첩되어있는지를 확인하는 문제이다. 따라서, stack을 활용하여 문제를 풀이하면 된다.
더 자세한 내용들은 위의 링크로 이동하여 확인해보길 바란다.
문제 풀이- 시간 복잡도 O(n)
def solution(S):
# Implement your solution here
temp = []
if len(S) == 0 :
return 1
for i in S:
if i == "(" or i=="[" or i=="{":
temp.append(i)
elif len(temp) == 0 :
return 0
if i == ")":
latest =temp.pop()
if latest != "(":
return 0
if i == "]":
latest = temp.pop()
if latest != "[":
return 0
if i == "}":
latest = temp.pop()
if latest != "{":
return 0
if len(temp) == 0 :
return 1
else:
return 0 📌 고려해야할 점
- for문을 돌면서 bracket의 시작 즉, "(", "[", "{" 가 들어가면 temp에 append 해준다.
- 만약, bracket의 닫는 부분 즉, ")", "]", "}" 가 들어오면 temp의 가장 최근에 들어온 문자열을 pop 한 후에 비교하여 최종 answer를 return 해준다.
- 처음 들어온 리스트가 빈 리스트일 때, 이 문제에서 정답으로 처리한다.
🙄 느낀 점
간단하게 stack을 이용하면 되는 문제이다.
