[LeetCode] 155번 (Min Stack)

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

Min Stack - LeetCode

---

🤣 문제 설명

• push, pop, top, getMin 을 지원하는 스택을 디자인 해야한다.
• MinStack()은 스택 생성자이다.
• push()는 top 인덱스에 val 요소를 추가한다.
• pop()은 스택의 top 인덱스 요소를 제거한다.
• top()은 스택의 top 인덱스 요소를 반환한다.
• getMin() 은 스택의 요소들 중 가장 작은 값을 반환한다.
• 각 함수들은 시간 복잡도가 O(1) 이어야 한다.
• pop, top and getMin 함수들은 항상 스택이 비어있지 않을 때 실행된다.
• -231 <= val <= 231 - 1
• At most 3 * 104 calls will be made to push, pop, top, and getMin.

 

🥲 문제 해결

• ArrayList<Integer> 자료구조를 사용해 stack 을 구현하고, top 포인터 하나를 생성한다.
• 생성자로 stack 과 top 포인터를 초기화한다.
• push 는 top++ 한 후 top 인덱스에 val 을 추가한다.
• pop 은 top 인덱스 값을 삭제한 후 top-- 한다.
• getMin 은 Collections.min() 을 사용한다.

 

😊 시간복잡도

O(1) 이다. 다만 getMin() 은 Collections.min() 이므로 O(n)이 걸린다.

이 부분이 런타임의 시간 대부분을 잡아먹는거 같다.

조건에서 생각해보니 O(1)이 걸려야된다고 했었는데, getMin() 은 생각하지 못 했었다.

이 부분은 min 에 대한 자료구조 하나가 더 필요할 거 같다.

 

😇 공간복잡도

ArrayList 하나를 생성했기 때문에 O(n)이다. 

 

🙂 정답

class MinStack {

    private ArrayList<Integer> stack;
    private int top;
    
    public MinStack() {
        this.stack = new ArrayList<>();
        this.top = -1;
    }
    
    public void push(int val) {
        this.top++;
        stack.add(top, val);
    }
    
    public void pop() {
        stack.remove(top);
        this.top--;
    }
    
    public int top() {
        return stack.get(top);
    }
    
    public int getMin() {
        return Collections.min(stack);
    }
}

 

😉 개선사항

• 위에서 말했듯이 자료구조가 하나 더 필요하다. 그래야 getMin() 메서드의 시간복잡도를 O(1) 로 맞출 수 있다.
• int min = 999999; 로 초기화 한 후, 사용하면 되지 않을까 생각했는데 해당 요소를 pop 하게 되면 다음으로 작은 요소를 가르킬 수 없기 때문에 ArrayList<> 자료구조가 필요할 거 같다.

class MinStack {

    private ArrayList<Integer> stack;
    private ArrayList<Integer> min;
    private int top;
    private int minTop;
    
    public MinStack() {
        this.stack = new ArrayList<>();
        this.min = new ArrayList<>();
        this.top = -1;
        this.minTop = -1;
    }
    
    public void push(int val) {
        this.top++;
        stack.add(top, val);
        
        int v = stack.remove(top);
        this.top--;
        if(min.contains(v)) {
            int i = min.indexOf(v);
            min.remove(i);
            this.minTop--;
        }
    }
    
    public void pop() {
        if(min.contains(stack.get(top))) {
            int i = min.indexOf(stack.get(top));
            if(i==minTop) {
                this.minTop--;
            }
            min.remove(i);
        }

        stack.remove(top);
        this.top--;
    }
    
    public int top() {
        return stack.get(top);
    }
    
    public int getMin() {
        return min.get(minTop);
    }
}

• min 을 추가해서 test Case 에 통과했지만, Submit 에서는 Testcase 4번째에서 실패했다. indexOutOfBoundsException 이 발생했다. 알고리즘에 문제가 없다 생각했지만, 문제가 있었다.
• 중복된 값이 stack 에 들어올 때 최소값이라면 min 에는 하나의 값만 들어온다. 해당 요소를 pop 하고 getMin() 을 요청하면 indexOutOfBoundsException 이 발생할 수 있다. 때문에 조건문에서 중복된 요소인지 아닌지를 체크한 다음에 min 에 요소에도 삭제할 것인지 체크해야한다. 체크하니 정상적으로 실행되었으며 430ms 에서 5ms 로 개선되었다.
• 시간복잡도도 O(n) 에서 O(1) 로 개선되었다.

class MinStack {

    private ArrayList<Integer> stack;
    private ArrayList<Integer> min;
    private int top;
    private int minTop;
    
    public MinStack() {
        this.stack = new ArrayList<>();
        this.min = new ArrayList<>();
        this.top = -1;
        this.minTop = -1;
    }
    
    public void push(int val) {
        this.top++;
        stack.add(top, val);
        
        if(min.isEmpty()) {
            this.minTop++;
            min.add(minTop, val);
        } else if(val < min.get(minTop)) {
            this.minTop++;
            min.add(minTop, val);
        }
    }
    
    public void pop() {
        int v = stack.remove(top);
        this.top--;
        if(min.contains(v) && !stack.contains(v)) { //변경부분
            int i = min.indexOf(v);
            min.remove(i);
            this.minTop--;
        }
    }
    
    public int top() {
        return stack.get(top);
    }
    
    public int getMin() {
        return min.get(minTop);
    }
}