Week 1-2. [Stack] 155. Min Stack (Python3)

문제 해결 과정

✍️ 나만의 방식으로 문제 정리하기 (=체계화)

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

Min Stack - LeetCode

push, pop, top, 최솟값을 가져올 수 있는 스택 자료구조를 구현하라.

• O(1)의 시간복잡도를 가지도록 구현해야 한다.

 

🔎 어떤 식으로 접근했는가?

리스트를 이용하여 스택을 모방했다.

스택에서의 최솟값을 가져오기 위해 값을 추가할 때 "현재 스택에서의 최솟값"까지 튜플 형태로 함께 추가한다.

 

스택이 LIFO(값을 스택 중간에서 꺼낼 수는 없다)이기 때문에 가능한 방법이다.

📝 의사 코드

class MinStack:

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

    def push(self, val: int) -> None:
        if self.stk에 기존 원소가 존재하면:
            (val, 스택 최솟값) 추가
        존재하지 않으면:
            (val, val) 추가

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

    def top(self) -> int:
        스택 상단 원소가 가지고 있는 값(0) 리턴

    def getMin(self) -> int:
        스택 상단 원소가 가지고 있는 최솟값(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()

 

🎯 구현 코드

class MinStack:

    def __init__(self):
        self.stk = [] # 리스트로 스택 자료구조 모방

    def push(self, val: int) -> None:
        if self.stk: # 스택에 추가되는 요소는 튜플 형태 (val, 현재 스택에서 최솟값)
            self.stk.append((val, min(val, self.stk[-1][1]))) # 기존 최솟값(self.stk[-1][1])과 val을 비교해 더 작은게 min_val
        else:
            self.stk.append((val, val)) # 스택이 비어있다면 최솟값은 val
        

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

    def top(self) -> int:
        return self.stk[-1][0] # top 원소의 값 (val)
        

    def getMin(self) -> int:
        return self.stk[-1][1] # top 원소에 저장된 최솟값 (min_val)


# 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()

 

내 코드를 탐구해보기

⏱ 성능 측정 (시간복잡도/공간복잡도)

시간 복잡도는 O(1)이다.

 

✍️ 성능 회고

스택에 각 요소를 튜플 형태로 저장하여 상수 시간에 반환할 수 있도록 했다.

 

다른 사람의 코드를 탐구해보기

🎯 구현 코드

나는 하나의 스택(stk)을 활용했지만, getMin() 메서드를 위해 min_stk을 하나 더 활용할 수 있다.

stk에 새로운 요소가 추가될 때, min_stk에 현재 스택에서 최솟값을 추가한다. (제거될 때도 마찬가지로 두 스택 모두에서 제거한다.)

getMin()을 호출할 때 min_stk에서 가장 상단 요소를 리턴한다.

class MinStack:

    def __init__(self):
        # 일반 스택
        self.stk = []
        # 최솟값 스택
        self.min_stk = []

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

    def pop(self) -> None:        
        self.min_stk.pop()
        return self.stk.pop()
        
    def top(self) -> int:
        return self.stk[-1]

    def getMin(self) -> int:
        # 최솟값 스택의 상단을 리턴
        return self.min_stk[-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()

 

⏱ 성능 측정 (시간복잡도/공간복잡도)

마찬가지로 O(1)의 시간 복잡도를 가진다.

 

느낀 점

파이썬으로 클래스를 구현하는 것이 조금 낯설었다.

getMin() 함수를 통해 최솟값을 O(1)에 가져오기 위해서 신경썼다.

 

참고 자료

LeetCode 풀기 - 155. Min Stack