3.2 스택 min

문제 

기본적인 push와 pop기능이 구현된 스택에서 최솟값을 반환하는 min함수를 추가하려고한다. 어떻게 설계할 수 있는가? push, pop, min 연산은 모두 O(1)시간에 동작해야한다. 

 

접근법

1. minValue 변수를 두고 minValue가 제거되면 다음 minValue를 탐색한다. -> push와 pop이 O(1)에 연산이 불가능

 

2. 스택에 각 상태값(minValue)를 함께 저장해두기 

class MinStack :
    def __init__(self):
        stack = []

    def push(self, num):
        if len(stack) == 0 :
            stack.append((num, num))
        else :
            cur_min = min(stack[-1][1], num)
            stack.append((num,cur_min))

    def min(self):
        return stack[-1][1]

    def pop(self):
        return stack.pop()[0]

 

3. minValue만을 저장하는 stack을 만들기 

class MinStack :
    def __init__(self):
        stack = []
        min_stack =[]
    
    def push(self, num):
        if num < min_stack[-1]:
            min_stack.append(num)
        stack.append(num)

    def min(self):
        return min_stack[-1]
    
    def pop(self):
        cur_num = stack.pop()
        if cur_num == min_stack[-1]:
            min_stack.pop()
        return cur_mum