[155. Min Stack] (알고리즘)

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.

스스로 고민

• 최소값을 반환하는 스택만들기
• 스택을 만든 후에 최소 값을 만들어주는 내장 함수를 만들어주면 된다.

접근법

• 스택을 구현하지만 어떻게 하면 최소 값만 쏙 빼올 수 있을까?

  의사코드

• 처음 초기 값에 min 값을 저장할 수 있도록 만들어준다.
• pop 또는 push 연산자를 할 때 내부에서 최소 값이 조건에 맞으면 업데이트 하게 만들어준다.
• 실제로 불러올 때는 getMin 함수로 초기 값에 저장되어 있는 최소 값을 빼와준다.

구현 코드

class MinStack:

  

    def __init__(self):

        self.items = []

        self.current = []

        self.min = []    

  

    def is_empty(self):

        return len(self.items) == 0

  

    def push(self, item):

        self.items.append(item)

        self.current = item

        if len(self.min) == 0:

            self.min = self.min.append(item)

        elif self.min > item:

            self.min = self.min.append(item)        

    def pop(self):

        if not self.is_empty():

            self.current = self.items.pop()

            self.min = min(self.current, self.min)

            return self.current

  

    def top(self):

        if not self.is_empty():

            return self.items[-1]

  

    def getMin(self):

        if self.min != None:

            return self.min

        else:

            return null

TypeError: object of type 'NoneType' has no len() if len(self.min) == 0: Line 14 in push (Solution.py) result = obj.push( Line 42 in __helper_select_method__ (Solution.py) ret.append(__DriverSolution__().__helper_select_method__(method, params[index], obj)) Line 98 in _driver (Solution.py) _driver() Line 107 in <module> (Solution.py)

• 라는 오류가 생겼는데 이해가 가지 않았다.
• 왜 None 이 뜰까?

my_list = []
result = my_list.append(10)

print(result)  # Output: None
print(my_list)  # Output: [10]

• None 값을 반환 하는 이유는 위와 같았다.
• 아직 파이썬에 대해서 잘 몰라서 접한 오류였다.
• 위와 같이 my_list를 출력해야 결과 같이 나오지 10을 넣는 행위는 반환 값이 None 이다.

    def pop(self):

        if not self.is_empty():

            self.current = self.items.pop()

            self.min = min(self.current, self.min)

            return self.current

• 이 부분에 대해서 아래와 같은 오류가 났다.

TypeError: [-2, -3] is not valid value for the expected return type integer raise TypeError(str(result) + " is not valid value for the expected return type integer") Line 65 in __helper_select_method__ (Solution.py) ret.append(__DriverSolution__().__helper_select_method__(method, params[index], obj)) Line 98 in _driver (Solution.py) _driver() Line 107 in <module> (Solution.py) During handling of the above exception, another exception occurred: TypeError: '<' not supported between instances of 'int' and 'list' Line 14 in _serialize_int (./python3/__serializer__.py) Line 63 in _serialize (./python3/__serializer__.py) return __Serializer__()._serialize(result, "integer"); Line 63 in __helper_select_method__ (Solution.py)

• 위 상황에서는 리스트인 상태에서 사용하는 게 아니라 값 자체로 비교해야하는데 리스트끼리 비교해서 이렇게 되었다. 그래서 리스트 저장 방법이 아닌 최솟값을 변수로 설정해서 다시 해봤다.

class MinStack:

    def __init__(self):
        self.items = []
        self.min = None

    def is_empty(self):
        return len(self.items) == 0

    def push(self, item):
        self.items.append(item)
        if self.min is None or item < self.min:
            self.min = item

    def pop(self):
        if not self.is_empty():
            popped_item = self.items.pop()
            if popped_item == self.min:
                self.update_min()
            return popped_item

    def top(self):
        if not self.is_empty():
            return self.items[-1]

    def getMin(self):
        return self.min

    def update_min(self):
        if not self.is_empty():
            self.min = min(self.items)
        else:
            self.min = None

• 리스트가 아닌 변수로 사용하고 update_min으로 min 값을 업데이트해준다.

  시간 복잡도와 공간 복잡도

시간 복잡도:

• push(), pop(), top(), getMin() 메서드에서는 주요 작업으로 리스트에 요소를 추가하거나 삭제하는 동작이 수행된다. 이러한 동작은 리스트의 끝에서 일어나며, 리스트의 길이가 n이라고 할 때 O(1)의 시간이 소요된다.
• update_min() 메서드에서는 min() 함수를 사용하여 리스트의 최솟값을 계산한다. min() 함수는 모든 요소를 순회하여 최솟값을 찾는 연산을 수행하므로 O(n)의 시간이 소요된다.

따라서 주어진 코드 전체의 시간 복잡도는 최악의 경우 O(n) 다.

공간 복잡도:

• self.items 리스트는 요소들을 저장하기 위한 공간을 필요로 한다. 최악의 경우 n개의 요소를 저장해야 하므로 O(n)의 공간이 소요된다.
• self.min 변수는 최솟값을 저장하기 위한 변수로서 추가적인 공간을 필요로 하지 않습니다. 따라서 O(1)의 공간이 소요된다.

종합하면, 주어진 코드의 공간 복잡도는 O(n)이며, 시간 복잡도는 O(n) 다.

회고 과정

다른 사람 코드를 보고 그 기준으로 어떤 부분을 개선 할 수 있는지 최종 회고

class MinStack:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.stack = []
        self.min_stack = []

    def push(self, val: int) -> None:
        self.stack.append(val)
        val = min(val, self.min_stack[-1] if self.min_stack else val)
        self.min_stack.append(val)


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

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

    def getMin(self) -> int:
        return self.min_stack[-1]

• getMin 의 경우 O(1) 로 이전 코드의 O(n) 보다 더 좋은 성능을 갖고 있다.
• 그 이유는 min_stack에 최솟 값이 업데이트 되기 전에는 현재 최솟 값을 stack 과 같이 넣기 때문이다.
• 검색하는 연산 작용을 없애기 위해서 자료구조를 활용했다고 생각한다.
• 알고 있는 게 많아야 생각하고 응용할 수 있는 폭이 넓어지는거 같다.