Skip to main content

Min Stack

문제​

스택을 설계하세요. 이 스택은 push, pop, top, 그리고 상수 시간 내에 최소 요소를 검색하는 기능을 지원해야 합니다.

MinStack 클래스를 구현하세요.

  • MinStacK()은 스택 객체를 초기화합니다.
  • void push(int val)은 val 요소를 스택에 푸시합니다.
  • void pop()은 스택의 맨 위 요소를 제거합니다.
  • int top()은 스택의 맨 위 요소를 가져옵니다.
  • int getMin()은 스택 내의 최소 요소를 검색합니다.

각 함수에 대해 O(1)의 시간 복잡도로 해결책을 구현해야 합니다.

접근 방향​

배열을 사용하여 스택을 구현하되 스택의 언더플로우를 확인하기 위해서 포인터를 사용한다. 포인터는 최초 -1로 초기화하고 push 메서드를 사용하여 스택에 요소가 추가될 시에 포인터를 증가하여 가장 위의 인덱스를 포인터가 가리키도록 한다. 요소를 제거할 때에는 현재 스택의 포인터가 -1 초과할 경우 스택에 요소가 있다는 것을 의미하므로 요소를 제거한 뒤 포인터를 1 차감한다. top 메서드는 현재 인스턴스 변수인 포인터가 가장 끝에 있는 인덱스를 가리키므로 스택 배열에 포인터 인덱스로 요소를 리턴하고 getMin 메서드의 경우 기본 함수 min()을 사용하여 인스턴스 변수 stack의 최솟값을 반환한다. 여기서 핵심 포인트는 포인터를 사용하여 가장 끝에 있는 인덱스를 가리키도록 하고 이 인덱스 위치에 따라 현재 스택에 요소의 삽입 여부를 확인한다.

나의 풀이​

class MinStack(object):
    # 멤버 변수로 stack 배열과 pointer를 초기화합니다.
    # pointer 변수의 경우 요소가 추가될 때 인덱스 0을 가리키도록 하기 위해 -1로 초기화
    def __init__(self):
        self.stack = []
        self.pointer = -1

    # 스택에 요소가 들어왔을 때 배열에 값을 삽입하고, 포인터를 1 증가
    def push(self, val):
        """
        :type val: int
        :rtype: int
        """
        self.stack.append(val)
        self.pointer += 1

    # 스택의 가장 마지막 요소를 제거할 때, 배열 안 요소 여부를 확인한 뒤 제거하고 포인터 1 차감
    def pop(self):
        """
        :rtype: int
        """
        if self.pointer > -1:
            self.stack.pop()
            self.pointer -= 1

    # 포인터는 항상 스택의 마지막 요소를 가리키므로 멤버 변수 포인터를 인덱스 값으로 갖는 요소 반환
    def top(self):
        """
        :rtype: int
        """
        return self.stack[self.pointer] if self.pointer > -1 else None

    # min() 함수로 현재 멤버 변수 stack 배열에 값이 존재할 경우 최솟값 반환
    def getMin(self):
        """
        :rtype: int
        """
        return min(self.stack) if self.pointer > -1 else None

다른 사람의 풀이​

class MinStack(object):
  def __init__(self):
    # 스택의 요소를 담을 stack 변수와 스택의 요소 중 최솟값을 담을 mins 변수를 초기화
    self.stack = []
    self.mins = []

  def push(self, val):
    # 멤버 변수 스택 배열에 요소 추가
    self.stack.append(val)

    # 멤버 변수 mins 배열에 요소가 존재하지 않거나, 추가하려는 요소가 mins 배열의 값 중 가장 작은 값보다 작을 경우 mins 배열에 추가
    if not self.mins or val <= self.mins[-1]:
      self.mins.append(val)

  def pop(self):
    # 가장 끝에 있는 요소를 제거 및 반환
    v = self.stack.pop()
    # 제거할 요소가 멤버 변수 mins의 최솟값과 같을 경우
    # 해당 요소는 더 이상 최솟값이 될 수 없으므로 mins 배열에서 제거
    if v == self.mins[-1]:
      self.mins.pop()

  # 멤버 변수 스택 배열의 마지막 요소 반환
  def top(self):
    return self.stack[-1]

  # 마지막 요소에 최솟값을 가지는 mins 배열에서 마지막 요소 반환
  def getMin(self):
    return self.mins[-1]

위 코드는 멤버 변수로 mins라는 배열을 하나 더 생성하여 메모리 공간을 더 사용하였으며 mins 배열의 마지막 요소에는 멤버 변수 stack 배열의 가장 작은 값이 들어가도록 하며 이를 위해 push 메서드에서 요소가 추가될 때 mins 배열의 마지막 요소와 비교하여 추가하려는 요소가 더 작다면 mins 배열에 추가하거나 pop 메서드의 경우 제거하려는 요소가 mins 배열의 마지막 요소와 동일하다면 더 이상 최솟값으로 유지할 수 없으므로 동일하게 mins 배열에도 제거를 하는 방식으로 스택을 구현한 모습입니다.