[알고리즘/Python] LeetCode 155. Min Stack 풀이 - 스택 두개 사용/ 스택 하나만 사용

📑 1. 문제 이해

https://leetcode.com/problems/min-stack/?envType=study-plan-v2&envId=top-interview-150 

Min Stack - LeetCode

  이 문제는 특별한 형태의  스택 자료구조를 구현하는 것입니다. 스택이면서 스택에 있는 원소들 중 최소값을 O(1) 시간에 계산할 수 있는 자료구조 입니다. 스택의 특성에 맞게 Last In, First Out 데이터를 삽입, 삭제 할 수 있도록 데이터를 삽입/삭제할 수 있도록 push(), pop(), top()의 연산을 구현하고, Stack 원소들 중 최소값을 구하는 getMin()연산을 구현해야합니다.

 

 스택의 최대 사이즈는 정해지지 않고 최대 push연산이 3 * 10^4번 일어날 수 있습니다. 빈 배열에 대해서 pop(), top(), getMin() 연산이 일어나지 않으므로 Stack Underflow 예외를 처리할 필요가 없습니다.

☑️ 테스트케이스

Input은 연산을 나타내는 문자열로 이루어져 있습니다. 각 문자열에 대응하는 함수가 호출될때 그 함수의 반환값들을 배열로 만들어 반환합니다. 반환값이 없다면 null을 반환합니다.

 

Example1:

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

output: [null, null, null, null, -2, null, 0, -1]

 

💡 2. 알고리즘 설계 - Stack 두개 사용.

 스택의 최소값을 구하는 것이 가장 어려운 부분입니다. Stack의 원소가 pop()될때마다 모든 원소들을 비교해서 최소값을 갱신한다면 getMin()의 시간복잡도는 O(N)이 될 것입니다.

 스택의 원소값을 저장하는 스택 이외의, 최소값을 기록하기 위해서 별도의 스택을 사용할 수 있습니다. 스택에 원소를 삽입할때 기존의 최소값과 비교해서 최소값 스택에도 원소를 삽입해 줍니다. 최소값 스택의 Top에 위치하는 원소는 현재 원소들 중 최솟값이 기록됩니다.

스택에서 원소를 삭제할때 최소값 스택에서도 하나를 삭제해줍니다. 그 결과로 최솟값 스택의 Top은 삭제된 원소를 제외하고 Stack에서 가장 작은 값을 나타냅니다.

 

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

    def push(self, val: int):
        self.stack.append(val)
        minValue = self.minValues[-1] if self.minValues and self.minValues[-1] < val else val
        self.minValues.append(minValue)

    def pop(self):
        self.minValues.pop()
        self.stack.pop()

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

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

시간 복잡도 및 공간 복잡도

시간 복잡도: O(1). 모든 연산의 시간복잡도는 O(1)이 됩니다. 배열의 끝에서 원소를 삽입/삭제하는 것은 나머지 원소들의 shift 연산이 필요 없어 O(1)연산이 됩니다. 최소값을 구하는 경우에도 최소값 스택의 Top 원소를 불러오면 되는 것으로 O(1) 연산이 됩니다.

공간 복잡도: O(N). 원소를 저장해둔 스택과 같은 크기의 최솟값 스택이 필요합니다. 

 ⎌ 3. 검토

테스트 케이스를 살펴보면 다음과 같습니다. 

 

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

output: [null, null, null, null, -2, null, 0, -1]

 

push() 연산이 3번 일어나고 난 후의 스택과, 최솟값 스택의 상태는 다음과 같습니다.

 현재 최소값은 -3이 됩니다.  이 상태에서 Pop()이 호출되면  스택, 최솟값 스택의 top에서 각각 하나씩 원소가 삭제됩니다.  이때 스택과 최솟값 스택의 상태는 다음과 같습니다.

 

 최솟값 스택의 top에는 [0, -2]에 대한 최솟값 -2가 기록되어 있습니다. 따라서, getMin() 호출시 최솟값 스택의 마지막 원소를 반환하면 됩니다.

---

🤔 다른 사람의 풀이 - 하나의 스택만 사용

 위의 풀이에서는 스택의 길이와 같은 길이의 최솟값 스택이 별도로 필요해, 원소의 개수가 많아지는 경우 메모리가 낭비된다는 단점이 있습니다. 수학적인 특성을 이용하면 하나의 스택만을 사용하여도 현재 최솟값과, 마지막 원소를 제외한 경우의 최소값을 구할 수 있습니다.

 push() 연산은 다음과 같이 진행합니다. 스택이 비어있거나, 스택의 최솟값보다 큰 값이 새롭게 삽입된다면 그 값 그대로 삽입합니다. 스택의 최솟값보다 더 작은 값이 새롭게 삽입되어 최솟값이 갱신되어야한다면 실제 값이 아닌 변형된 값 (2 * 실제값 - 최솟값) 을 저장합니다.  (2  * 실제값 - 최솟값) 은 항상 실제값보다 작습니다. 따라서 self.min에 저장된 값보다 작은값이 stack에 존재한다면 그 값은 실제 값이 아닌 변형된 값이라고 판단할 수 있습니다.

pop() 연산은 다음과 같이 진행합니다. 스택에서 빠진 값이 min에 저장된 값보다 작다면 최소값이 빠진 것입니다. 따라서 최소값을 이전 최소값을 갱신해주어야합니다. 이전 최소값은 다음과 같이 구합니다.

class MinStack2:
    EMPTY = 2 ** 31

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

    def push(self, val: int):
        if not self.stack:
            self.stack.append(val)
            self.min = val
        elif self.min <= val:
            self.stack.append(val)
        else:
            self.stack.append(2 * val - self.min)
            self.min = val

    def pop(self):
        x = self.stack.pop()
        if x < self.min:
            self.min = 2 * self.min - x

    def top(self) -> int:
        if self.stack[-1] < self.min:
            return self.min
        else:
            return self.stack[-1]

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

시간 복잡도 및 공간 복잡도

시간 복잡도: O(1). 모든 연산은 배열의 마지막에서 일어나며, 최솟값 계산시에도 별도의 배열 탐색 없이 수학적인 연산을 이용하므로 O(1) 시간이 걸립니다.

공간 복잡도: O(1). 여전히 스택 하나는 필요합니다. 하지만 실제로는 최솟값 스택이 필요없으므로 더 적은 메모리를 소비합니다.

---

✅ 정리

◎ 스택의 최소값을 계산하기 위해서는 현재 최소값 뿐 아니라 이전 원소까지의 최소값을 기억해두어야합니다. 그래야 원소가 pop()되고 난 다음의 최소값도 알 수 있기 때문입니다.

◎ 새로운 값으로 갱신하면서 이전 값도 기억해야할 필요가 있을때 수학적인 계산을 이용해서 수 하나에 함께 담을 수도 있습니다.