[LeetCode] 155. Min Stack

말하는 감자·2024년 12월 11일

data structure leetcode python stack 리트코드 스택 자료구조 코딩테스트 코딩테스트 준비 파이썬

LeetCode

목록 보기

31/32

이번 문제는 LeetCode에서의 스택 자료 구조 유형 문제입니다. 살펴볼까요?

1. 오늘의 학습 키워드

Stack

2. 문제: 155. Min Stack

단계: Medium
주제: Stack, Design
출처: https://leetcode.com/problems/min-stack/description/

Description

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:

$-2^{31}$ <= val <= $2^{31}$ - 1
Methods pop, top and getMin operations will always be called on non-empty stacks.
At most 3 * $10^4$ calls will be made to push, pop, top, and getMin.

3. 문제 풀이

Step1. 문제 이해하기

주어진 문제는 push, pop, top과 최솟값을 검색하는 getMin 함수들을 모두 $O(1)$ 의 시간복잡도로 구현해야 합니다.

입출력, 조건 및 제약들을 살펴보겠습니다.

push, pop, top, getMin함수들을 구현해야 합니다.
pop, top, getMin함수들은 항상 비워져 있지 않은 스택에서 호출된다고 합니다.
push함수의 매개변수인 val의 범위는 int형 값만 들어가는것을 의미합니다.
최대 3 * $10^4$ 번의 호출이 있습니다. 이는 $10^8$ 을 넘지 않고 각 함수들이 $O(1)$ 로 구현된다면 충분한 시간입니다.

Step2. 문제 분석하기

이 문제가 Medium난이도인것은 아무래도 최솟값을 바로바로 구해야 한다는 점에 있는것 같습니다. 또한 O(1)의 시간 복잡도로 구현해야 합니다. 이 뜻은 기본 스택에 값을 넣고 빼야 하지만, 최솟값만을 따로 저장하는 스택 자료구조 1개를 더 만들어야 한다는 것을 의미합니다.

왜냐하면 스택 자료구조에서 진행되는 함수들은 모두 O(1)의 시간 복잡도로 구현할 수 있습니다. 거기다 최솟값을 따로 저장할려면 최소값만을 담는 스택 자료구조를 따로 만든다면 해결할 수 있습니다.

그럼 이것을 기반으로 바로 코드 설계를 해보도록 하겠습니다.

Step3. 코드 설계하기

자료구조 선택:
- 기본 스택을 구현하기 위해 하나의 리스트를 사용 (self.stack).
- 최솟값을 관리하기 위해 별도의 리스트를 추가 (self.min_stack).
- min_stack에는 현재 스택의 최솟값만을 저장하여 최솟값을 $O(1)$ 시간에 조회 가능하도록 한다.
push 메서드:
- 새로운 값을 기본 스택에 추가.
- 만약 min_stack이 비어 있거나, 새로운 값이 min_stack의 최상단 값보다 작거나 같으면 min_stack에도 추가.
pop 메서드:
- 기본 스택에서 값을 제거.
- 제거된 값이 min_stack의 최상단 값과 동일하다면, min_stack에서도 제거.
top 메서드:
- 기본 스택의 최상단 값을 반환.
getMin 메서드:
- min_stack의 최상단 값을 반환하여 최솟값을 조회.

Step4. 코드 구현하기

class MinStack(object):

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

    def push(self, val):
        """
        :type val: int
        :rtype: None
        """
        self.stack.append(val)

        # 최솟값 스택 업데이트
        if not self.min_stack or val <= self.min_stack[-1]:
            self.min_stack.append(val)
        

    def pop(self):
        """
        :rtype: None
        """
        if self.stack:
            val = self.stack.pop()
            if val == self.min_stack[-1]:
                self.min_stack.pop()
        

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

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

코드 설명:
- push: 새로운 값을 기본 스택에 추가하고, 필요하면 min_stack에도 추가.
- pop: 기본 스택에서 값을 제거하고, min_stack에서도 최솟값이 제거되는 경우 처리.
- top: 기본 스택의 최상단 값을 반환.
- getMin: min_stack의 최상단 값을 반환해 $O(1)$ 시간에 최솟값을 조회.
시간 복잡도:
- push: $O(1)$ (값 추가 및 min_stack 업데이트)
- pop: $O(1)$ (값 제거 및 min_stack 업데이트)
- top: $O(1)$ (최상단 값 반환)
- getMin: $O(1)$ (최솟값 반환)
공간 복잡도:
- 두 개의 스택 사용: 입력된 값의 개수에 비례하여 $O(n)$ .
결과: https://leetcode.com/problems/min-stack/submissions/1476142188