#155 Min Stack

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

문제 조건

• -2^31 <= val <= 2^31 - 1
• 메서드 pop, top, getMin은 항상 비어 있지 않은 스택에서 호출된다.
• push, pop, top, getMin은 최대 3 * 10^4의 호출이 이루어진다.
  push, pop, top, getMin을 사용할 수 있는 MinStack 클래스를 구현한다.

문제 해결

문제 해결 로직

해당 문제는 기본적인 stack을 구현하되 현재 stack의 최솟값을 반환해야한다는 제약 조건이 있다.

틀렸던 case

기본적으로 배웠던 stack을 구현하기 위해 int 배열로 minStack을 구현하고 int lowestValue를 선언하여 최솟값을 관리하여 했으나 구현하면서 다음과 같은 문제점을 겪었고 해결 방법을 생각했다.

• 배열의 크기를 하드코딩으로 선언해야함.
  • 크기를 조절하기 쉽도록 ArrayList를 사용한다.
• pop을 하게 되었을 때 두번째로 작은 값을 찾아 lowestValue에 넣어주어야 함.
  • 해당 리스트의 위치값 마다 그 위치까지의 최솟값을 저장해둔다.

데이터 선언

minStack을 구현하기 위해 기본 데이터를 저장할 리스트와 해당 위치까지의 최소값을 저장한 리스트가 필요하다. 해당 데이터는 생성되면 할당하도록 한다.

• stack
  실제 값들을 저장할 리스트
• minValues
  해당 위치까지의 최솟값을 저장할 리스트

    public MinStack() {
        stack = new ArrayList<>();
        minValues = new ArrayList<>();
    }

push

데이터를 입력했을 때 다음과 같은 과정으로 진행한다.
1. 실제 값들을 저장하는 stack에 값 추가하기
2. 앞까지 저장되어있던 최솟값과 비교하여 더 작은 값을 현재 위치 최솟값으로 저장하기

    public void push(int val) {
        stack.add(val);
        if (minValues.isEmpty() || val <= minValues.get(minValues.size() - 1)) {
            minValues.add(val);
        } else {
            minValues.add(minValues.get(minValues.size() - 1));
        }
    }

pop

데이터를 pop했을 때 다음과 같은 과정으로 진행한다.
1. 실제 값들을 저장하는 stack에 맨 뒤의 값 삭제하기
2. 최소 값들을 저장하는 minValues에 맨 뒤의 값 삭제하기

    public void pop() {
      stack.remove(stack.size() - 1);
      minValues.remove(minValues.size() - 1);
    }

top & getMin

최근의 저장된 값과 최솟값은 각 리스트 맨 위의 값을 반환하면 된다.

    public int top() {
      return stack.get(stack.size() - 1);
    }

    public int getMin() {
      return minValues.get(minValues.size() - 1);
    }

코드 작성

class MinStack {
    private List<Integer> stack;
    private List<Integer> minValues;

    public MinStack() {
        stack = new ArrayList<>();
        minValues = new ArrayList<>();
    }

    public void push(int val) {
        stack.add(val);
        if (minValues.isEmpty() || val <= minValues.get(minValues.size() - 1)) {
            minValues.add(val);
        } else {
            minValues.add(minValues.get(minValues.size() - 1));
        }
    }

    public void pop() {
      stack.remove(stack.size() - 1);
      minValues.remove(minValues.size() - 1);
    }

    public int top() {
      return stack.get(stack.size() - 1);
    }

    public int getMin() {
      return minValues.get(minValues.size() - 1);
    }
}

복잡도 계산

• 시간 복잡도

  • 모두 바로 위치를 찾을 수 있기 때문에 상수(O(1))의 시간복잡도를 가진다.

• 공간 복잡도

  • stack 와 minValues에 저장된 요소의 개수와 공간 복잡도는 같아진다.
  • 따라서 공간 복잡도는 O(N)+O(N) = O(N)이다.

회고

• 다음과 같은 점수를 기록했다.
  

• ArrayList를 사용함으로 여러 장점을 얻을 수 있었다.

  • 크기를 동적으로 관리하여 크기 생각을 하지 않을 수 있음.
  • 기본적으로 제공하는 add(), remove(), isEmpty()를 사용할 수 있어 편리함.

• 하지만 더 고려해야할 것도 있었다.

  • 메모리 사용 면에서 두개의 리스트를 유지하는데 메모리 사용이 아쉬움.
  • 노드로 직접 구현하거나 다른 방법을 고려해보면 좋겠다.