🏷️155. Min Stack

---

1. 문제 설명

• 스택을 디자인하되, push, pop, top 및 최소 요소를 상수 시간에 검색할 수 있는 스택을 구현하십시오.

• MinStack 클래스를 구현하십시오:

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

• 각 함수에 대해 O(1) 시간 복잡도를 가진 솔루션을 구현해야 합니다.

---

2. 접근 방법

Stack 문제라 stack을 사용하지 않고 문제를 해결하려고 List를 활용하여 문제를 풀었습니다.

• 먼저 MinStack() 생성자를 List로 만듭니다.
• void push(int val) : .add(val)를 하여 변수를 순차적으로 저장합니다.
• void pop() : .remove(stack.size - 1)을 하여 마지막 데이터를 제거합니다.
• int top() : stack.get(stack.size() - 1)으로 마지막 데이터를 조회여 반환합니다.
• int getMin()은 스택에서 최소의 값을 반환해야 합니다.
  • 새로운 List 생성시 생성자를 이용하여 현재까지 저장한 stack을 복사합니다.
  • 복사한 새로운 List인 minStack을 오름차순 정렬을 합니다.
  • 그리고 나서 첫번째 index의 값을 반환하면 최소값을 반환하게 됩니다.

---

3. 구현 코드

class MinStack {

    List<Integer> stack;  
  
    public MinStack() {  
        stack = new ArrayList<>();  
    }  
  
    
    public void push(int val) {
        stack.add(val);
    }
    
    public void pop() {
        stack.remove(stack.size() - 1);
    }
    
    public int top() {
        return stack.get(stack.size() - 1);
    }
    
    public int getMin() {
        List<Integer> minStack = new ArrayList<>(stack);
        Collections.sort(minStack);
        return minStack.get(0);
    }
}

• 메소드 push(), pop(), top() 에서 시간 & 공간복잡도가 O(1)인데 getMin()에서 시간 & 공간복잡도가 O(n)으로 측정됩니다.

• 시간 복잡도 : O(n)
• 공간 복잡도 : O(n)

---

4. 개선 사항

해당 문제를 해결하결하고 통과를 했지만 각 함수에 대해 O(1) 시간 복잡도를 가진 솔루션을 구현해야 합니다. 라는 문제 내용을 충족시키 못했습니다.
그래서 getMin()을 O(1)의 시간 복잡도로 구현하기 위해 최소값을 저장하는 List minStack을 하나 더 추가하였습니다.

• 새로운 데이터를 push할 때 minStack이 비어있으면 추가를하여 최소값을 저장합니다.
• 또 새로운 데이터를 push하면 minStack에 최소값 데이터가 있으므로 새로운 값과 현재 최소값과 비교하여 더 작거나 같으면 minStack에 추가합니다.
• pop하면 최소값 스택 minStack에서 최소값을 비교합니다. 최소값이 같으면 minStack에서도 제거합니다.

class MinStack {

    List<Integer> stack;  
    List<Integer> minStack;  
    
    public MinStack() {  
        stack = new ArrayList<>();
        minStack = new ArrayList<>();
    }  
  
    public void push(int val) {
        stack.add(val);
         if (minStack.isEmpty() || val <= minStack.get(minStack.size() - 1))
            minStack.add(val);
    }
    
    public void pop() {
        if (stack.get(stack.size() - 1).equals(minStack.get(minStack.size() - 1)))
            minStack.remove(minStack.size() - 1);
        
        stack.remove(stack.size() - 1);
    }
    
    public int top() {
        return stack.get(stack.size() - 1);
    }
    
    public int getMin() {
        return minStack.get(minStack.size() - 1);
    }
}

• 시간 복잡도 : O(1)
• 공간 복잡도 : O(1)

---

5. 최종 회고

• 처음 제출하여 통과한 코드를 작성하는데 시간이 얼마 걸리지 않았지만 시간 복잡도를 충족하기 위해 리펙토링하는 시간이 많이 걸렸습니다. 어떻게 하면 O(1)으로 개선할 수 있을까 생각을 하면서 많은 시도를 했지만 아쉽게도 결국 다른 분들의 코드를 확인하고 해결할 수 있었습니다.
• 이번 문제는 저의 이해의 빈틈을 알려준 문제라고 생각합니다. 이해의 빈틈을 채우기 위해 체크를 해놓고 여러번 생각해보고 다시 풀어보려고 합니다.