[LeetCode] 155 - Min Stack

문제

 

 

스택을 구현하는 간단한 문제이다. 스택만을 구현하는 것은 간단하지만 스택에 들어있는 요소들의 최소값을 반환하는 메소드가 추가되어있어 이를 추가하는게 관건인 문제이다.

 

풀이(1)

class MinStack:

    def __init__(self):
        self.stack = []	#스택의 기능을 할 리스트 선언

    def push(self, val: int) -> None:
        self.stack.append(val)	#append() 이용하여 스택에 추가

    def pop(self) -> None:
        if self.stack :				#스택에 요소가 있어야 pop이 가능하므로
            return self.stack.pop()	

    def top(self) -> int:
        return self.stack[-1]		#리스트의 마지막 요소 (스택의 맨 위) 반환

    def getMin(self) -> int:
        return min(self.stack)		#스택을 구현하는 것이지만, 변수가 리스트이기 때문에 min 메소드 사용하여 반환

[Python] 선형 자료구조 : 배열, 링크드 리스트, 스택 , 큐 , 데크

[Python] 선형 자료구조 : 배열, 링크드 리스트, 스택 , 큐 , 데크

 

이전에 블로그를 작성하며 리스트로 스택을 구현하는 것을 해본 경험이 있기에, 그걸 토대로 스택 구현 완료, 최소값을 구하는 메소드의 경우에는 리스트의 min() 메소드를 이용했다. 

 

 

하지만 문제를 푼 사람들보다 런타임이 너무 길게 나왔고, 최소값을 구하는 메소드를 수행할 때 O(n)의 시간복잡도가 걸린다고 생각했고 시간복잡도의 문제라고 판단해 다른 코드를 생각했다.

 

풀이(2)

class MinStack:

    def __init__(self):
        self.stack = []
        self.stack_min = []		#최소값을 저장하는 스택 추가

    def push(self, val: int) -> None:
        self.stack.append(val)
		#최소값을 저장하는 스택에는 언제나 -1에 최소값이 들어있다
        if (not self.stack_min) or (val <= self.stack_min[-1]) :
            self.stack_min.append(val)

    def pop(self) -> None:
        if self.stack :
            popped = self.stack.pop()
            if popped == self.stack_min[-1] :	#pop한 최소값이 stack_min에 들어있는 최소값일때
                self.stack_min.pop()
            return popped
        else : 
            print("No element")		#stack에 아무것도 들어있지 않을 시에 경고문 추가

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

    def getMin(self) -> int:
        return self.stack_min[-1]		#시간복잡도 O(1)

 

min을 저장할 스택을 선언하는 코드를 새로 구현했다. push할 경우에 stack에는 일단 push하고, stack_min에 값이 들어있지 않을 경우나 새로 들어온 수가 최소값일 때, stack_min에 해당 요소를 추가해 stack_min[-1]에는 언제나 최소값이 들어있게 구현하였고, pop의 경우에는 pop한수가 stack_min[-1]과 같을 때 (최소값일 때) stack_min에서도 pop되게 구현하였다. 이렇게 하면 getMin()에서 self.stack_min[-1]을 반환하면 되므로 시간복잡도가 O(1)로 줄어들게 된다.

 

 

바꾼 코드의 런타임 결과. 런타임이 훨씬 좋아졌다 !