[Leetcode/파이썬] 155. Min Stack

Min Stack

---

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

• MinStack() initializes the stack object.
• void push(int val) pushes the element val onto the stack.
• void pop() removes the element on the top of the stack.
• int top() gets the top element of the stack.
• int getMin() retrieves the minimum element in the stack.

You must implement a solution with O(1) time complexity for each function.

 

Example 1:

Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output
[null,null,null,null,-3,null,0,-2]

Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top();    // return 0
minStack.getMin(); // return -2

 

Constraints:

• -231 <= val <= 231 - 1
• Methods pop, top and getMin operations will always be called on non-empty stacks.
• At most 3 * 104 calls will be made to push, pop, top, and getMin.

 

class MinStack:
    def __init__(self):
        self.minstack = []

    def push(self, val: int) -> None:
        return self.minstack.append(val)

    def pop(self) -> None:
        return self.minstack.pop()

    def top(self) -> int:
        return self.minstack[-1]

    def getMin(self) -> int:
        return min(self.minstack)


# 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()

네 이렇게 풀었는 당신. 오답입니다. 문제의 가장 마지막 문장을 보면, "You must implement a solution with O(1) time complexity for each function." 이라고 되어 있다. 당연히 저도 처음 풀었을 때, 이렇게 풀었다가 뭔가 이상함을 느끼고 문제를 다시 읽어보았다. 반드시 시간복잡도가 O(1)이 되는 풀이로 풀어보자. 

지금부터는 저의 생각이니 틀린 부분이 존재할 수 있으므로, 스터디 후나 댓글로 많은 지적 부탁드립니다.

지금 여기서 시간복잡도가 상수가 아닌 지점은 def getMin 부분이라고 판단된다. 그 이유는 다른 것은 [-1]에 해당하는 부분에 더하거나, 팝하거나, 가리키면 된다. min함수는 내부를 살핀 후 가장 작은 것을 반환해야 하므로, O(N) 까지도 떨어지는 그런 함수이다. 따라서 저 부분을 어떤 방식으로 해결해볼까를 생각해보아야 한다. 

class MinStack:

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

    def push(self, val: int) -> None:
        currMin = self.getMin()
        if val < currMin :
            currMin = val
        
        self.stack.append((val, currMin))

    def pop(self) -> None:
        self.stack.pop()
        

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

    def getMin(self) -> int:
        if not self.stack :
            return float('inf')
            
        return self.stack[-1][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()

다음과 같이 수정해보자. 다른 분의 코드를 참고하는 부분이 참 쉽지만 죄책감이 몰려오는 그런 부분이다. stack에는 (현재값, 현재까지 가장 작은값)을 input하게 될 것이라고 생각해보자. 그러면 getMin()은 자연스럽게 return self.stack[-1][1]을 해야할 것이다. 그리고 push 부분으로 올라가서 스택에서 현재 가장 작은 수를 꺼내고자 하였지만, 처음이라면 에러가 뜰 것이다. 지금 stack은 비어있으니까. 그래서 if문으로 현재 스택이 비어있으면 무한을 return 하라고 하였다. 

다시 push 부분으로 가서 현재 가장 작은 값을 찾고자 한다. 현재 들어온 값과 스택 안에 있는 가장 작은 값과 비교해보자. val이 더 작다면 현재 값을 currMin 을 val로 갱신해주고 stack에 (현재 값, 가장 작은값)을 묶어서 넣어주자. 만약 val이 가장 작은 값으로 갱신되었다면, (val, val) 아니라면 (val, 스택안에서 가장 작은값 = getMin)이 들어가게 될 것이다.

pop과 top은 가장 쉽다. 우리가 익히 알고 있는 pop()과 [-1]값을 return 해주면 된다. 여기서 top 은 현재값이기 때문에 self.stack[-1][0]을 해주어야 한다. 처음에 top이 현재 가장 큰 수라고 착각해서 max(stack)로 했다가 틀렸다. 

이렇게 하면 시간복잡도 O(1)인 함수가 하나 만들어 졌다.