[스택, Stack] 현재 시점의 최소값

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

문제를 처음 봤을 때는 "최소값을 저장하는 변수를 만들어 push, pop 시에 업데이트 해주면 되는거 아닌가?" 라고 생각했는데
그렇게 할 경우 O(1) 로 처리해야한다는 조건에서 pop시에 O(n)이 되어버릴 것 같았고,
그렇다고 별도의 array를 만들어 관리하자니 마찬가지로 O(n)이 되어버릴 것 같았다.

---

우선 기본 stack을 구현해보자.
stack은 배열을 이용해서 구현할 수 있다.

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

    def push(self, value):
        return self.stack.append(value)

    def pop(self):
        if not self.stack:
            return None
        return self.stack.pop()

---

여기서 min을 추가하면 다음과 같다.
min 값 추적을 위해 따로 추가적으로 stack을 사용하였다.
이 stack의 용도는 stack에 쌓여있는 값을 순서대로 저장하거나 하는 용도가 아니다.
해당 시점에서의 min 값을 보관하는 목적으로 사용된다.

class Stack:
    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, value):
        self.stack.append(value)
        if not self.min_stack or value <= self.min_stack[-1]:
            self.min_stack.append(value)

    def pop(self):
        if not self.stack:
            return None
        if self.stack[-1] == self.min_stack[-1]:
            self.stack.pop()
        return self.stack.pop()

    def min(self):
        if not self.min_stack:
            return None
        return self.min_stack[-1]

pop 수행 시 해당 값이 min 일 경우에만 min_stack에서 값을 제거한다.

 

python list pop

Remove the item at the given position in the list, and return it. If no index is specified, a.pop() removes and returns the last item in the list. (The square brackets around the i in the method signature denote that the parameter is optional, not that you should type square brackets at that position. You will see this notation frequently in the Python Library Reference.)

• 아무 값도 넣지 않을 경우 마지막 아이템 제거
• 음수를 넣을 경우 뒤에서부터 제거
  • 예시
    • pop(-1) : 뒤에서 첫번째 (아무 값도 넣지 않았을 경우와 동일)
    • pop(-3) : 뒤에서 세번째

python 양의 무한, 음의 무한

양의 무한 : float('inf')
음의 무한 : float('-inf')

math 모듈의 math.inf, -math.inf 를 사용하는 방법도 있음.

파이썬에서 배열이 비어있는걸 확인하는 두 가지 방법

array = []

not array # return True
len(array) == 0 # return True