[leetcode][Medium][Stack] 155. Min Stack 풀이, 해설 (python)

https://leetcode.com/problems/min-stack/

Min Stack - LeetCode

 

 

1차 풀이

가벼운 스택 문제일거라 생각했는데, getMin 부분에서 어떻게 O(1)을 만들까 잠깐 고민했다. 

그러다가 어처피 스택이니까 그때마다 최솟값을 저장해두고 pop시 같이 pop해주면 될것 같다는 생각에 아래처럼 구현했다. 

class MinStack(object):

    def __init__(self):
        self.minStack = [sys.maxsize] 
        self.stack = [] 

    def push(self, val):
        """
        :type val: int
        :rtype: None
        """
        if (self.minStack[-1] > val):
            self.minStack.append(val)
        else:
            self.minStack.append(self.minStack[-1])
        self.stack.append(val)
        

    def pop(self):
        """
        :rtype: None
        """
        self.stack.pop()
        self.minStack.pop()

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

    def getMin(self):
        """
        :rtype: int
        """
        return self.minStack[-1]
        
        


# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

 

 

 

 

해설 

https://www.youtube.com/watch?v=qkLl7nAwDPo

동일하게 minStack을 만들어서 진행했다. 

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

    def push(self, val):
        """
        :type val: int
        :rtype: None
        """
        self.stack.append(val)
        val = min(val, self.minStack[-1] if self.minStack else val) # minStack 값이 있을때만 
        self.minStack.append(val)
        

    def pop(self):
        """
        :rtype: None
        """
        self.stack.pop()
        self.minStack.pop()

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

    def getMin(self):
        """
        :rtype: int
        """
        return self.minStack[-1]