[leetcode - Java] 155. Min Stack

1. 문제

---

- 상수 시간 안에 push, pop, top, 최소 원소 검색을 제공하는 stack을 설계하라

Stack 이란?

후입선출(LIFO / Last-In-First-Out): 최근 추가된 요소가 먼저 제거되고 먼저 추가된 요소가 나중에 제거된다. 이해하기 쉬운 예시로 식당에 줄을 서있는데 늦게 온 사람이 먼저 들어가는 것 이라고 생각하면 된다. 즉 출입구가 하나인 박스에 요소를 쌓는 것이다.

push : 스택에 data 넣음.
pop : 스택 맨 위의 data 제거. -> 가장 마지막에 push 한 data가 가장 먼저 pop 된다.
peek : pop과 유사하게 맨 위의 data 반환 -> 스택에서 제거되지 않음.
top : 가장 마지막에 추가된 data의 위치 (가장 맨위)

2. 의사 코드

---

1. Linked List에 사용될 head노드(dummy)를 만든다
    private Node dummy;
2. dummy 기본 구성 요소 생성
    static class Node {
        최솟값
        노드의 값
        다음 노드 주소값

        public Node(최솟값, 노드값, 주소값) {
        노드 생성자로 최솟값, 노드값, 다음 주소값 초기화
        }
    }
3. MinStack 생성자로 노드 초기화.
    MinStack() {
    dummy = new Node(최솟값(초기 큰 수), 노드값, 주소값);
    }
4. push 과정에서 매개변수와 현재의 min을 비교하여 min 업데이트 & 노드 생성
    최솟값 = Math함수로 매개변수 val과 비교하여 저장
5. pop
    다음 노드로 넘어가 값 제거
6. top
    현재 stack의 위에있는 값 반환
7. getMin
    현재 노드의 최솟값 반환

3. 시도

---

class MinStack {
    private Node dummy;

    public MinStack() {
        dummy = new Node(Integer.MAX_VALUE, 0, dummy);
    }

    public void push(int val) {
        int min = Math.min(dummy.min, val);
        dummy = new Node(min, val, dummy);
        // System.out.println("min = " + min);
        // System.out.println("data = " + dummy.data);
    }

    public void pop() {
        // System.out.println("pop = " + dummy.data);
        dummy = dummy.next;
    }

    public int top() {
        // System.out.println("top = " + dummy.data);
        return dummy.data;
    }

    public int getMin() {
        // System.out.println("getMin = " + dummy.min);
        return dummy.min;
    }

    static class Node {
        int min;
        int data;
        Node next;

        Node(int min, int data, Node next) {
            this.min = min;
            this.data = data;
            this.next = next;
        }
    }
}

단방향 Linked List에서 각 노드별로 최솟값을 업데이트 해주는 방식이다. 코드를 작성하며 생각난 다른 방법이 있는데 일반적인 매개변수가 담기는 Stack 하나와 min 변수가 담기는 또 다른 Stack, 총 2개의 스택을 만들어 각 메서드별로 실행하면 될 것 같았다. 구현해본 코드는 아래와 같다.

class MinStack {
    private Stack<Integer> stack;
    private Stack<Integer> minStack;

    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
        minStack.push(Integer.MAX_VALUE);
    }

    public void push(int val) {
        stack.push(val);
        int min = Math.min(getMin(), val);
        minStack.push(min);
        // System.out.println("stack = " + stack);
        // System.out.println("min = " + min);
        // System.out.println("minStack = " + minStack);

    }

    public void pop() {
        stack.pop();
        minStack.pop();
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }

}