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.

 

 

 

 

풀이

 

 

모든 동작을 O(1)로 동작하는 스택을 구현하는 문제이다.

 

기본적으로 스택으로 만들어야하는데 만들고나니 큐처럼 만들어버렸다. 

 

node객체를 통해서 data,next,prev,min을 가지게 되고 push할 때마다 노드를 생성하여 min값 모든 노드가 가지도록 만들었다.

 

pop을 O(1)의 시간복잡도로 구현하기 위해서 tail을 사용하여 뽑아낼 수 있지만 . 이후에 연달아 pop을하게되면 tail을 가르키는 주소가 맞지 않아서 오류가 나는 부분을 수정하기 위해 생각하다 node의 객체에 node인덱스의 앞방향을 가르키는 주소를 prev로 지정하여 넣었다 . (prev와 next  두 개 모두 사용했다. 이 부분에서 생긴 문제를 찾지 못해서 한시간은 찾은거같다 )

 

다른 부분은 모두 다 동작하는데 어느 순간 테스트케이스에서 pop을 통해서 스택을 모두게되면 NoneType의 최소값을 찾지 못했다. 알고보니 나는 tail을 통해서 마지막인자의 최소값 stack.tail.min을 사용하는데, 최초의 코드에서는 단순히 tail을 변경하게되고 마지막 node가 비워지게된다면 head의 값도 none이 되어야하는데 none이 아니라 스택에 인자가 있다는 가정하에 if문을 피하여 진행되어서 NoneType에서 min 값을 찾을 수 없다는 오류가 계속해서 나왔던 것이다.

 

이후에 코드를 수정하고 통과에 성공했다.

 

 

 수정하기 전의 최초의 코드 
 
    def pop(self):
        self.tail = self.tail.prev
         #마지막 head =None  #tail값을 tail.prev로 변경
        # self.tail.next = None # 변경된 tail의 next None으로 지정
        
        
스택의 head를 초기화 해주는 코드를 추가
    def pop(self):
        if self.tail.prev ==None: # 스택의 마지막 인자 (prev = None일 경우 스택의 헤드 초기화)
            self.head =None
            return
        self.tail = self.tail.prev
         #마지막 head =None  #tail값을 tail.prev로 변경
        # self.tail.next = None # 변경된 tail의 next None으로 지정

 

 

class Node:
    def __init__(self,data): 
        self.data = data # 노드값 
        self.next = None # 최초 생성시 다음 노드 지정안함
        self.min = None
        self.prev = None

class MinStack(object):
    def __init__(self):
        self.head =None #스택 생성시 시작부분 설정 (아직 값이 없기에 None)
        self.tail = None

    def push(self, val):
        node = Node(val)
        node.min = val
        if self.head == None: #문제의 로직 -> pop을 할 때 마지막인자라면 head도 초기화해주도록하자.
            node.min= val
            self.head = node
            self.tail = node
            return
        node.min = min(self.tail.min,val) #최소값 노드에 저장 
        node.prev = self.tail
        self.tail.next = node
        self.tail = node
        
        

    def pop(self):
        if self.tail.prev ==None: # 스택의 마지막 인자 (prev = None일 경우 스택의 헤드 초기화)
            self.head =None
            return
        self.tail = self.tail.prev #마지막 head =None 
        print(self.tail.min) #tail값을 tail.prev로 변경
        # self.tail.next = None # 변경된 tail의 next None으로 지정

        """
        :rtype: None
        """
        

    def top(self):
        return self.tail.data
        """
        :rtype: int
        """
        

    def getMin(self):
        return self.tail.min

 

 

 

다른사람의 코드

 

class MinStack:
    def __init__(self):
        self.A = []
        self.M = []
    def push(self, x):
        self.A.append(x)
        self.M.append( x if not self.M else min(x, self.M[-1]) )
    def pop(self):
        self.A.pop()
        self.M.pop()
    def top(self):
        return self.A[-1]
    def getMin(self):
        return self.M[-1]

내장된 리스트를 사용해서 구현했다.

 

사실 이렇게 풀 수도 있었지만 , 아마 이렇게 직접 리스트를 구현하고 스택을 구현하라는 의도로 출제한 것을 알기에 

전에 배웠던 내용을 활용해서 풀었다.  구현하고나니 이해도가 더 높아진 것 같다. 굳!