[Leetcode] - 20

• 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