- stack 은 python 의 list로 구현
- python 의 list는 동적리스트
- stack 의 push, pop 시간복잡도
- O(1)
- 동적리스트는 메모리가 부족하면 필요한 메모리를 추가로 할당 (2배씩 증가)
- 메모리를 추가로 할당할 때 전체 리스트를 복사하기 때문에 insert의 시간복잡도는 O(N)
- 메모리 doubling은 어쩌다 한번 일어남
- Amotrized time complexity
- 최악의 경우의 시간복잡도를 전체에 걸쳐 나눠주는식으로 알고리즘의 시간복잡도를 계산
- 항상 최악을 가정하고 시간복잡도를 계산하는것은 적절하지 않기 때문
- insert의 최악의 경우 시간복잡도 O(N)을 전체에 걸쳐나눠줘야함
- 따라서 insert의 시간복잡도는 O(1)
class Solution:
def isValid(self, s: str) -> bool:
stack = []
table = {
')':'(',
'}':'{',
']':'[',
}
for c in s:
if c not in table:
stack.append(c)
elif not stack or table[c] != stack.pop():
return False
return len(stack) == 0