[리트코드] 155. Min Stack

문제

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

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

 

• -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.

---

✔ 문제접근 #1 min 함수사용 [통과] ⭕, 모든 요구사항 충족 ❌

Intuition

python의 min함수를 이용하여 현재 스택의 최솟값을 구한다.push, pop의 경우 list가 내부적으로 동적배열이기 때문에 append()와 pop()을 활용한다.

Algorithm
두개의 배열의 시작점에 각각 p1, p2의 포인터를 갖는다. 그리고 nums1의 삽입할 위치 idx를 갖는다.

p1, p2를 비교하여 더 작은 숫자를 nums1 배열의 idx위치에 넣는다. 그리고 더 작은 숫자가 있었던 쪽읜 포인터 p1을 +1 증가시키고, idx 도 +1 증가 시킨다.

이렇게 병합정렬에서 사용하는 merge알고리즘을 사용하여 오름차순으로 배열을 만들 수 있다.

class MinStack:

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

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

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

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

    def getMin(self) -> int: # O(N)
        return min(self.data)

실행결과

 

Complexity Analysis

• 시간 복잡도 : O(N**2)
  • 스택을 호출하는 횟수 O(N)
  • 최악의 경우 모든 호출이 getMin()이 된다면 O((N*N + 1)/2)
  • 그러므로 전체 시간복잡도 : O(N**2)

• 공간복잡도 : O(N)

---

✔ 문제접근 #2 stack 활용 [통과] ⭕, 모든 요구사항 충족 ⭕

Intuition
현재 스택 데이터들의 최솟값을 별도의 스택 형태의 자료구조로 관리해준다.

최솟값 스택의 최상단 값이 현재 스택들의 최솟값을 의미한다.

Algorithm

문제접근1의 스택 구현에서 최솟값을 관리해줄 수 있는 min_stack을 선언한다.push메서드를 통해 데이터가 들어올 때마다 min_stack함수의 가장 상단에 있는 데이터와 비교하여 같거나 작으면 삽입해준다.pop메서드를 통해 현재 빠져나가는 데이터와 min_stack의 함수의 가장 상단에 있는 데이터와 같은 수라면 data와 min_stack 상단의 데이터 모두를 삭제한다.

class MinStack:

    def __init__(self):
        self.data = []
        self.min_stack = []
        

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

    def pop(self) -> None:
        if self.data[-1] == self.min_stack[-1]:
            self.min_stack.pop()
            
        self.data.pop()
            

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

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

실행결과

Complexity Analysis

• 시간 복잡도 : O(N)
  • 스택을 호출하는 횟수 O(N)
  • 각 메소드 연산 O(1)
  • 그러므로 전체시작복잡도 : O(N*1) = O(N) -> 실제 실행시간도 풀이1) 보다 훨씬 줄어들었다.

• 공간복잡도 : O(N)
  
  • 추가적인 최솟값을 관리해줄 배열을 하나 선언하므로 O(N + N) = O(N)

---

기타풀이 및 회고

stack의 특징을 활용함으로써 현재 최솟값보다 더 큰 숫자들을 배재하고 시작한다. 그 이유는 pop연산시에 최댓값이 아닌 수들은 빠져나가도 현재 스택의 최솟값에 영향을 미치지 않기 때문이다.

주의할 점은 11번째 줄의 self.min_stack[-1] >= val: 부분에서 등호를 넣어주지 않는다면, pop연산시에 해당하는 최솟값이 내가 들어올 때 생긴 최솟값과 일치하는지 모르기 때문에 문제를 해결할 수 없다.

 

스택은 배울때의 간단함과 실제 문제에 응용할때의 난이도차이가 상당하다고 생각하기 때문에 여러 활용방법에 익숙해지는 것이 좋을 것 같다.