[Stack] Min Stack

1. 문제

LeetCode - Min Stack

• push, pop, top 및 일정한 시간에 최소 요소 검색 getMin을 지원하는 스택 MinStack을 설계하는 문제
• 각 기능에 대해 O(1) 시간 복잡도를 갖는 솔루션을 구현해야 하는 제약조건이 있다.

2. 접근법

• ArrayList와 직접 구현한 Node로 해결하는 방법으로 먼저 접근 -> 실패
• java.util.Stack 자료구조 및 최소값을 기록할 min을 사용하여 테스트 통과

3. 해결 코드

class MinStack {

    // 각 메서드는 O(1)의 시간 복잡도를 가져야 한다.

    private Stack<Integer> stack;
    private int min; // getMin() 호출 시 반환해야 할 stcak의 최소값 기록

    public MinStack() {
        stack = new Stack<>();
        min = Integer.MAX_VALUE; // 일단 정수 최대값으로 초기화
    }
    
    public void push(int val) {
        // 만약, val이 min보다 작거나 같다면(최소값 갱신해야 하는 상황)
        if (val <= min) {
            // stack에 min 추가 및 min을 val로 갱신
            stack.push(min);
            min = val;
        }
        // stack에 val 추가
        stack.push(val);
    }
    
    public void pop() {
        // pop하려는 값이 최소값과 같다면 MinStack의 min 갱신 필요
        if (stack.pop() == min) {
            // 한번 더 pop해서 min 갱신
            min = stack.pop();
        }
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return min;
    }

}

4. 성능

- Runtime : 4ms

- Memory : 40.6mb

5. 실패한 풀이

import java.util.ArrayList;

class MinStack {

    private ArrayList<Node> stack;
    private int pointer;

    public MinStack() {
        this.stack = new ArrayList<>();
        this.pointer = -1;
    }

    public void push(int val) {
        Node node = new Node(val);

        // 첫 노드일 때
        if (stack.isEmpty()) {
            node.setMin(val);
        } else { // 그렇지 않을 때
            Node prev = stack.get(pointer);
            node.setMin(Math.min(prev.getMin(), val));
        }

        stack.add(node);
        pointer++;
    }

    public void pop() {
        if (stack.isEmpty()) {
            throw new RuntimeException("empty stack");
        }
        stack.remove(pointer);
        pointer--;
    }

    public int top() {
        if (stack.isEmpty()) {
            throw new RuntimeException("empty stack");
        }
        Node removedNode = stack.remove(pointer);
        pointer--;
        return removedNode.getData();
    }

    public int getMin() {
        if (stack.isEmpty()) {
            throw new RuntimeException("empty stack");
        }
        return stack.get(pointer).getMin();
    }

    static class Node {

        private int data;
        private int min;

        public Node(int data) {
            this.data = data;
        }

        public int getData() {
            return data;
        }

        public void setData(int data) {
            this.data = data;
        }

        public int getMin() {
            return min;
        }

        public void setMin(int min) {
            this.min = min;
        }

    }

}