[LeetCode 해석 및 풀이] 155. Min Stack

LeetCode 문제 해석 및 풀이 방법

 

문제 155. Min 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.

 

한글

push, pop, top, 그리고 현재 가장 작은 값을 검색해주는 stack을 설계해세요

 

MinStack 클래스 구현

• MinStack() : stack 개체를 초기화합니다.
• void push(int val) : 원소 val을 스택에 push합니다
• void pop() : stack 맨위에 있는 원소를 제거합니다
• int top() : stack 맨 위에 있는 원소를 체크합니다.
• int getMin() : stack 안에서 가장 작은 원소를 검색합니다.
• 모든 함수는 O(1)의 시간복잡도를 가져야 합니다.

 

제한조건

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

 

입출력 예

입력	출력
["MinStack","push","push","push","getMin","pop","top","getMin"] [[],[-2],[0],[-3],[],[],[],[]]	[null,null,null,null,-3,null,0,-2]

 

 

해답 및 해설

파이썬 (Python)

class MinStack:
    def __init__(self):
        self.main_stack = []
        self.min_stack = []

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

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

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

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

숫자들을 저장하는 스택과 최소값만을 저장하는 스택을 따로 만들어둔다. 값을 넣을 때는 지금까지 최소값을 넣어둔 스택과 현재 들어간 값을 비교하여 더 낮은 값을 최소값 스택에 넣는다.