41. Min Stack

문제

MinStack 클래스를 구현하시오.

단, push(), pop(), top(), getMin() 메서드 모두 시간 복잡도가 O(1)이라야 한다.

(pop은 마지막 요소를 삭제, top은 마지막 요소를 읽기만 함)

 

해결 방식

MinStack 클래스의 프로퍼티로 stack 리스트 하나와 min 리스트 하나, 총 두 개의 리스트를 만든다.

stack에 값을 삽입할 때마다 min에도 값을 삽입한다.

단 min에는 스택의 마지막 요소와 value 중 더 작은 값을 삽입한다. 

pop을 할 때도 stack과 min을 같이 pop 한다.

=> min 스택의 마지막 요소는 항상 최소값으로 유지됨

class minStack:
    def __init__(self):
        self.stack = []
        self.min = []

    def push(self, value):
        self.stack[-1] = value

        # min 스택에도 똑같이 값 하나를 삽입
        # 단, min 스택의 마지막 요소와 value 중 더 작은 값을 선택해서 삽입
        # 즉 min 스택의 마지막 요소는 항상 최소값으로 유지됨
        self.min[-1] = value if not self.min else min(value, self.stack[-1])
        
    def pop(self):
        self.stack.pop()
        self.min.pop()

    def top(self):
        return self.stack[-1]

    def getMin(self):
        return self.min[-1]