LeetCode 풀기 - 155. Min Stack

155. Min Stack

https://leetcode.com/problems/min-stack/

Min Stack - LeetCode

문제)

솔루션1)

• 두 개의 스택 활용(Normal Stack, Min Stack)
• Normal Stack에 요소가 추가될 때 Min Stack에는 현재의 min 요소를 추가
• getMin() 호출 시 Min Stack에서 가장 상단의 요소를 리턴하면 됨.

class MinStack:

    def __init__(self):
        # 일반 스택
        self.arr = []
        
        # 최소값 스택
        self.min_arr = []
        

    def push(self, val: int) -> None:
        # 일반 스택에 추가
        self.arr.append(val)
        
        if len(self.min_arr) == 0:
            # 최소값 스택에 비어 있으므로 그냥 추가
            self.min_arr.append(val)
        else:
            # 가장 상단의 값과 현재 추가되는 값의 최소값을 최소값 스택에 추가
            self.min_arr.append(min(val, self.min_arr[-1]))
        

    def pop(self) -> None:        
        self.min_arr.pop()
        return self.arr.pop()
        

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

    def getMin(self) -> int:
        # 최소값 스택의 상단을 리턴
        return self.min_arr[-1]
        


# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

솔루션2)

• 스택을 하나만 사용
• 스택에 추가되는 요소는 튜플(val, min val) 형태

class MinStack:

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

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

    def pop(self) -> None:                
        return self.arr.pop()
        

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

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