리트코드 155. Min Stack JAVA

문제

문제 해석

1. Min값을 바로 확인할 수 있는 스택을 만들어라
2. 시간복잡도는 항상 O(1)이 걸려야한다.
3. 핵심 조항
   • Methods pop, top and getMin operations will always be called on non-empty stacks.
   • 즉 pop, top, getMind을 할 때는 항상 스텍이 가득 차 있다.
     • 예외처리를 할 필요가 없다.

문제를 보면 일단 pop, top, getMind에서 예외처리를 할 필요가 없다.

이미 구현 되어 있는 스택을 이용해서 코드를 구현할 수 도 있지만 LinkedList를 만들 때 처럼 Node를 직접 만들어서 스택을 구현하고자 한다.
* 이미 구현 되어 있는 스택을 이용한다면 이 것은 굳이 문제를 풀 이유가 별로 없다고 생각이 들었기 때문이다.
* Stack<Integer[]> stack ; 이런 식으로 선언 하면 쉽게 풀 수 있기 때문이다.

수도 코드

    Node node;

    public MinStack() {
        더미 노드 생성
        더미노드 생성 시 min 값은 MAX 값으로 
    }

    public void push(int val) {
        더미노드가 존재하기 때문에 if문을 사용할 이유가 없다.
        새로운 노드를 만들어서 값 대입
        node.right = new Node(val, Math.min(val,node.min));
        임시 코드 구현해 현재 node 임시 보관
        Node tmp = node;
        node = node.right;
        node.left = tmp;
    }

    public void pop() {
        노드 이동  / 문제에서 예외처리 없어도 된다 명시 -> 예외처리 불필요
        node = node.left;
        node.right = null;
    }

    public int top() {
    문제에서 예외처리 없어도 된다 명시 -> 예외처리 불필요
        return node.val;
    }

    public int getMin() {
    문제에서 예외처리 없어도 된다 명시 -> 예외처리 불필요
        return node.min;
    }
}
노드 생성
class Node{
    int min;
    int val;
    Node left;
    Node right;

    public Node(int num, int min){
        this.val = num;
        this.min = min;
    }
    public Node(){
        this.min = Integer.MAX_VALUE;
    }
}

수도 코드를 구현하다 보니 코드가 얼추 다 완성되었다.
데이터의 삽입은 left -> right 로 흘러간다.

코드

class MinStack {

    Node node;

    public MinStack() {
        //더미노드
        node = new Node();
    }

    public void push(int val) {
        node.right = new Node(val, Math.min(val,node.min));
        Node tmp = node;
        node = node.right;
        node.left = tmp;
    }

    public void pop() {
        if(node == null)
            return;
        node = node.left;
        node.right = null;
    }

    public int top() {
        return node.val;
    }

    public int getMin() {
        return node.min;
    }
}
class Node{
    int min;
    int val;
    Node left;
    Node right;

    public Node(int num, int min){
        this.val = num;
        this.min = min;
    }
    public Node(){
        this.min = Integer.MAX_VALUE;
    }
}

간단하게 코드를 구현할 수 있었다.
결과를 확인해 보면

메모리를 많이 사용하고 있음을 알 수 있다.

다른 사람 솔루션 [메모리 적게사용]

class MinStack {

    int min;
    int top;
    int[] stack;
    int[] minarr;

    public MinStack() {
        min=Integer.MAX_VALUE; top=-1; stack= new int[100000];
        minarr= new int[10000];
    }

    public void push(int val) {
        stack[++top]= val;
        if(top==0){
        min= val;
           minarr[top]= val; 
        }
        else{
            min= Math.min(minarr[top-1], val);
            minarr[top]= min;
        }
    }

    public void pop(){
        if(top!=-1){
             top--;
        }
    }

    public int top() {
        return stack[top];
    }

    public int getMin() {
        if(top==-1){ return -1;}
        return minarr[top];
    }
}

나와 다르게 배열을 통해 값을 저장했다.
min값은 minarr의 index를 나타내는 값이다.

이렇게 2개의 배열을 사용해서 코드를 구현할 경우 빠르게 값을 파악할 수있다.
배열을 이용한 방법을 고민했었는데 많은 참고를 할 수 있었다.
배열을 만들어서 스택처럼 사용하는 것은 과거 파이썬을 공부할 때 적응하려고 노력했던 방법이었다.
파이썬은 따로 스택을 제공해주지 않기 때문에 그런 방법을 썼던 것 같은데 그 덕분에 코드를 빠르게 해석할 수 있었다.

다른 사람 솔루션 Pair 사용

class MinStack {
    private Stack<Pair<Integer, Integer>> stack;

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

    public void push(int val) {
        if (stack.isEmpty()) {
            stack.push(new Pair<>(val, val));
        } else {
            int min = Math.min(stack.peek().getValue(), val);
            stack.push(new Pair<>(val, min));
        }
    }

    public void pop() {
        if (!stack.isEmpty()) {
            stack.pop();
        }
    }

    public int top() {
        if (stack.isEmpty()) {
            return 0;
        }
        return stack.peek().getKey();
    }

    public int getMin() {
        if (stack.isEmpty()) {
            return 0;
        }
        return stack.peek().getValue();
    }
}

일단 코드를 해석하기 전에 Pair라는 클래스 자체를 처음 본다.

Pair클래스 확인
We can find the Pair class in the javafx.util package. The constructor of this class takes two arguments, a key and its corresponding value:
javafx.util.package 에 있는 클래스로 2개의 요소를 가지고 있으며, 각각 키벨류로 이루어져있다.

Pair<Integer, String> pair = new Pair<>(1, "One");
Integer key = pair.getKey();
String value = pair.getValue();