[leetCode 155] Min Stack (Java)

1.문제

Min Stack - LeetCode

Min Stack - LeetCode

 

---

2.문제설명

 

간단하게 MinStack class를 구현하면 된다.

1. Minstack 기본 생성자 : stack 객체를 초기화한다.
2. void push(int val) : val 을 stack에 추가한다.
3. void pop() : stack에서 top 요소를 제거한다.
4. int top() : stack에서 top 요소를 리턴한다.
5. int getMin() : 현재 스택에서 가장 최소값을 반환한다

 

---

3.소스코드

class MinStack {

    private Stack<Node> stack;
    class Node{
        int val;
        int min;

        public Node(int val, int min) {
            this.val = val;
            this.min = min;
        }
    }
    public MinStack() {
        stack = new Stack<>();
    }

    public void push(int val) {
        if(stack.size() == 0){
            stack.push(new Node(val,val));
        }
        else{
            int minVal;
            if(val < stack.peek().min){
                minVal = val;
            }else{
                minVal = stack.peek().min;
            }
            stack.push(new Node(
                    val,
                    minVal
            ));
        }
    }

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

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

    public int getMin() {
        return stack.peek().min;
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

---

3-1.코드해설

 최솟값을 구하는 스택을 구현하라는 문제 이다. 기본적인 Stack<> 라이브러리와 ArrayList , List , Node 로 풀 수있다. stack의 push와 pop은 계속 변할 수 있으므로 Deque 와 우선순위 큐를 사용하여도 풀수 있다.

 

나는 Node 를 활용하여 최솟값 계산을 빠르게 할려 Node 를 구현 하여 풀었다.

 

Node 에 val 와 min 값을 구현 하고 push 할 때 최솟값을 비교하며 push를 하게 구현하였다. 

 

---

5.회고

 

 

결과는 생각 했던 것보다.. 속도와 메모리 측면에서 잡지를 못했다. 

Node를 사용하여 직접 접근하여 컨트롤 한다면 기본 Stack 과 큐/데크 보다는 빠를거라고 생각 했지만 생각했던 것 보다 느리고 메모리는 많이 차지했다.. 

 

class MinStack {

    int min;
    Node head;
    Node dummy;

    class Node {
        int val;
        Node next;
        int prevMin;
        Node(int val, Node next, int prevMin) {
            this.val = val;
            this.next = next;
            this.prevMin = prevMin;
        }
    }

    public MinStack() {
        dummy = new Node(Integer.MAX_VALUE,null,Integer.MAX_VALUE);
        head = dummy;
        min = dummy.val;
    }
    
    public void push(int val) {
        Node node = new Node(val, head, min);
        if (val < min) {
            min = val;
        }
        head = node;
    }
    
    public void pop() {
        if (head.val == min) {
            min = head.prevMin;
        }
        head = head.next;
    }
    
    public int top() {
        return head.val;
    }
    
    public int getMin() {
        return min;
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

다른 사람들의 코드를 참고 하였을 때 , Stack 을 사용 하지 않고 Node 를 직접 구현하였다는 것을 보고 참고하여 다시 한번 개선 해보았다.

class MinStack {

    private Node head;

    private class Node {
        int val;
        int min;
        Node next;

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

    public MinStack() {
        head = null;
    }

    public void push(int val) {
        if (head == null) {
            head = new Node(val, val, null);
        } else {
            int newMin = Math.min(val, head.min);
            head = new Node(val, newMin, head);
        }
    }

    public void pop() {
        if (head != null) {
            head = head.next;
        }
    }

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

    public int getMin() {
            return head.min;
    }
}

 

위 코드를 참고하여 개선 해보았을 때 성공이였다. 

불필요한 초기화 와 dummy를 head로 잡으면서 직접 구현한 Node를 구현하여 속도와 메모리 측면에서 좀더 개선 할 수 있었다. 

 

Node를 직접 구현하면서 node 에대한 지식도 많이 습득했던 경험 같다.