LeetCode[ 155 | Python ] Min Stack

문제

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

push, pop, top과 최소 요소를 상수 시간안에 반환할 수 있는 스택을 구현하는 문제.

풀이

시도

실행 시간 : 46ms
메모리 : 17.8MB

스택은 선형으로, 스택안에 새로 들어올 원소의 값이 최소 값이라면 점점 최소값은 줄어나아가되 더이상 증가하지는 않는다.
이러한 점에 착안하여 기준이될 최소값을 정의하고 새로운 요소가 입력됐을 때의 최소값을 함께 저장해주는 방식을 사용했다.

• push : 기준 최소값 min_val과 비교하여 min_val을 갱신하고, 스택에 함께 넣어준다.
• pop : 현재 스택의 값이 min_val과 같고 현재 스택에 남아있는 값이 없다면 min_val을 초기화한다. 현재 스택에 값이 남아있다면 다음 원소의 최소 값으로 min_val을 갱신한다.
• top : 가장 마지막 값을 꺼내지 않고 return 한다.
• getMin : 가장 마지막 원소에 저장되어있는 최소값을 꺼내지않고 return 한다.

class MinStack(object):
    min_val = None
    stk = None

    def __init__(self):
        self.min_val = float('inf')
        self.stk = []

    def push(self, val):
        self.min_val = min(val, self.min_val)
        self.stk.append([val, self.min_val])
        
    def pop(self):
        x = self.stk.pop()
        if x[0] == x[1]:
            if len(self.stk) > 0:
                self.min_val = self.stk[-1][1]
            else:
                self.min_val = float('inf')
        

    def top(self):
        return self.stk[-1][0]
        

    def getMin(self):
        return self.stk[-1][1]
 

개선 1

실행 시간 : 35ms
메모리 : 17.3MB

스택에 존재하는 각 원소마다 리스트를 따로 가지는 것이 메모리를 더 사용한다고 생각되어 스택과 동기화 되어있는 최소값들의 스택 mins를 정의했다.
여러개의 리스트를 사용하지 않고, 하나의 리스트 만을 이용하므로 메모리 사용률을 감소시킬 수 있었다.

• push : min_val을 새로운 값과 비교하여 새로운 값은 스택에, 최소값은 mins에 저장한다.
• pop : mins 와 스택에서 각각 값을 하나씩 추출한다. 이 때 mins 가 비어있으면 min_val을 초기화 하고, 그렇지 않다면 다음 원소로 갱신한다.
• top : 스택의 다음 원소를 꺼내지 않고 return 한다.
• getMin : mins의 다음 원소를 꺼내지 않고 return 한다.

class MinStack(object):
    min_val = None
    stk = None
    mins = None

    def __init__(self):
        self.min_val = float('inf')
        self.stk = []
        self.mins = []

    def push(self, val):
        self.min_val = min(val, self.min_val)
        self.mins.append(self.min_val)
        self.stk.append(val)
        
    def pop(self):
        x = self.stk.pop()
        y = self.mins.pop()
        if x == y:
            if len(self.mins) > 0:
                self.min_val = self.mins[-1]
            else:
                self.min_val = float('inf')
        

    def top(self):
        return self.stk[-1]
        

    def getMin(self):
        return self.mins[-1]
        

개선 2

실행 시간 : 44ms 메모리 : 17.1MB

개선 1 에서 작성한 코드를 보아하니 기준 최소값 min_val을 이용할 필요도 없다는 생각이 들었다.
이미 현재의 최소 값은 mins에 저장되어 있기 때문에, 이 값을 이용하기로 했다.

코드 실행시 마다 약간의 차이는 있었지만, 덕분에 개선 2 에서의 코드가 평균적으로 가장 적은 메모리 사용률을 보였다.

class MinStack(object):
    stk = None
    mins = None

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

    def push(self, val):
        if len(self.mins) > 0:
            self.mins.append(min(val, self.mins[-1]))
        else:
            self.mins.append(val)
        self.stk.append(val)
        
    def pop(self):
        x = self.stk.pop()
        y = self.mins.pop()

    def top(self):
        return self.stk[-1]
        

    def getMin(self):
        return self.mins[-1] 

생각 & 정리

원티드 백엔드 인턴십 강의를 수강하며
BUD 라는 것에 대해서 알게 되었다.

• Bottlenecks : 병목 현상을 일으키는 곳
• Unncessary work : 불필요한 작업이 일어나는 곳
• Duplicated work : 중복된 작업이 일어나는 곳

근래 문제들을 해결해나아가며 내가 생각하던 것들이, 생각해야 하는 것들이 어떤 것인지 명확해지는 내용이었다.

물론 해당 포스트에서의 문제가 어려운 문제는 아니었지만, 처음부터 최적의 솔루션을 찾아내겠어 ! 라는 생각으로 접근하기보다는 가장 무식한 방법으로라도 솔루션을 찾고 그 솔루션을 최적화해 나아가며 개선하는 방식으로 접근하는 것이 좋겠다는 생각이 들었다.

또한 그 접근을 유지하는 습관을 가지면서 다양한 방법론을 떠올리기도, 여러 접근법을 떠올리기도 할 것이라고 생각된다.

(이 문제에서는 중복된 작업을 최대한 제거해 나아갔다.)