LeetCode - 155.Min Stack (JVM 의 메모리 Saving 이슈)

[Must-do Easy Question] 시리즈

How to effectively use LeetCode to prepare for interviews!! - LeetCode Discuss

 

https://leetcode.com/problems/min-stack/

Min Stack - LeetCode

---

문제

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

• push(x) -- Push element x onto stack.
• pop() -- Removes the element on top of the stack.
• top() -- Get the top element.
• getMin() -- Retrieve the minimum element in the stack.

 

Example:

MinStack minStack = new MinStack();

minStack.push(-2); minStack.push(0);

minStack.push(-3); minStack.getMin(); --> Returns -3.

minStack.pop();

minStack.top();                                    --> Returns 0.

minStack.getMin();                              --> Returns -2.

 

---

push, pop top, 최소값을 구하는 기능을 constant time에 동작하는 Stack을 구현하는게 문제이다.

 

알고리즘 보다는 Stack 자료구조 문제인 것 같다.

 

제일 단순하게 ArrayList를 이용해 구현해 봤다.

import java.util.*;
class MinStack {

    ArrayList < Integer > stack = new ArrayList();
    /** initialize your data structure here. */
    public MinStack() {

    }

    public void push(int x) {
        stack.add(x);
    }

    public void pop() {
        stack.get(stack.size() - 1);
        stack.remove(stack.size() - 1);
    }

    public int top() {
        return stack.get(stack.size() - 1);
    }

    public int getMin() {
        int min = stack.get(0);
        for (int i = 1; i < stack.size(); i++) {
            if (min > stack.get(i)) {
                min = stack.get(i);
            }
        }
        return min;
    }
}

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

일단 통과했다.

Success Details  Runtime: 117 ms, faster than 6.69% of Java online submissions for Min Stack. Memory Usage: 41.4 MB, less than 10.15% of Java online submissions for Min Stack.

그러나 약 7퍼센트 빠르고 10퍼센트의 메모리 효율을 보인다. 

좀더 빠르고 효율적인 코드가 필요하다.

 

스택문제에 스택을 사용해도 되나..?

스택을 사용해 보았다. 그런데 getMin()이 제대로 동작하지 않는다.

import java.util.*;
class MinStack {

    Stack<Integer> stack = new Stack();
    int min;
    /** initialize your data structure here. */
    public MinStack() {

    }

    public void push(int x) {
        if (stack.isEmpty()){
            min = x;
        }
        
        if(x < min){
            min = x;   
        }
        stack.add(x);
    }

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

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

    public int getMin() {
        return min;
    }
}

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

 

문제는 min을 구할때 push 에서 값을 update 해주었는데 pop 할때도 min 값을 update 해 주어야 한다는걸 깜빡했다.

 

그럼 min 값을 순서대로 가지고 있어야 pop 된 min 값 이전의 값을 찾을 수 있는데,,

 

제일 먼저 생각난 것은 stack 을 하나 서 만들어서 min 값들을 push 해주는 거였다. 근데 stack 2개는 쓰기 싫다..

 

stack 2개 쓰지뭐...

import java.util.*;
class MinStack {

    Stack<Integer> stack = new Stack();
    Stack<Integer> min = new Stack();
    /** initialize your data structure here. */
    public MinStack() {

    }
    
    public void push(int x) {
        stack.push(x);
        if(min.isEmpty()){
            min.push(x);
        }else if(x <= min.peek()){
            min.push(x);
        }

        System.out.println(min);

    }

    public void pop() {
        if(stack.pop() == min.peek()){
            //update min
            min.pop();
        }
    }

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

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

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

틀렸다..

마지막 getMin에서 잘못되는 것 같다. 

 

분명히 min 스택은 512 -1024 -1024 로 있다가 pop 두번해서 512가 남게되는거 같은데 pop 이 제대로 안되는 것 같다.

 

다른 사람의 정답 코드를 봐도 다른게 없는데 틀린 답이 나온다..

 

혹시나 해서 int x 를 선언하여 따로 stack.pop() 을 담고 그걸 min.peek() 와 비교하게 고쳤더니.....

통과....

엥?

 

import java.util.*;
class MinStack {

    Stack<Integer> stack = new Stack();
    Stack<Integer> min = new Stack();
    /** initialize your data structure here. */
    public MinStack() {

    }
    
    public void push(int x) {
        stack.push(x);
        if(min.isEmpty()){
            min.push(x);
        }else if(x <= min.peek()){
            min.push(x);
        }

        System.out.println(min);

    }

    public void pop() {
        int x = stack.pop();
        if(x== min.peek()){
            //update min
            min.pop();
            System.out.println(min);

        }
    }

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

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

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

if(stack.pop() == min.peek()) 	//false
-----------------------------
int x = stack.pop()
if (x == min.peek())			//true

이 둘의 결과값이 다르다?!

 

pop의 Return Value는 peek()와 같은데...

[똑같은 질문을 한 사람이 있다]

WEIRD DIFFERENCE: int popped = stack.pop() vs stack.pop() in if statement - LeetCode Discuss

 

https://stackoverflow.com/questions/3130311/weird-integer-boxing-in-java/3130348#3130348

Weird Integer boxing in Java

비슷한 질문을 찾았다.

public class Scratch
{
   public static void main(String[] args)
    {
        Integer a = 1000, b = 1000;  //1
        System.out.println(a == b);

        Integer c = 100, d = 100;  //2
        System.out.println(c == d);
   }
}
Output:

false
true

이런 기이한 현상을 볼 수가 있다. 

== 대신에 .equals를 쓰면 비교가 잘 된다!

왜 때문일까

 

---

Yep the first output is produced for comparing reference; 'a' and 'b' - these are two different reference. In point 1, actually two references are created which is similar as -

Integer a = new Integer(1000);

Integer b = new Integer(1000);

The second output is produced because the JVM tries to save memory, when the Integer falls in a range (from -128 to 127). At point 2 no new reference of type Integer is created for 'd'. Instead of creating a new object for the Integer type reference variable 'd', it only assigned with previously created object referenced by 'c'. All of these are done by JVM.

These memory saving rules are not only for Integer. for memory saving purpose, two instances of the following wrapper objects (while created through boxing), will always be == where their primitive values are the same -

• Boolean
• Byte
• Character from \u0000 to \u007f (7f is 127 in decimal)
• Short and Integer from -128 to 127

첫번째 a 와 b를 비교한 아웃풋은 reference를 비교해서 나온 결과값이다. 이 둘은 다른 reference를 가지고 있다.  1의 시점에서 사실 두개의 reference가 

Integer a = new Integer(1000);

Integer b = new Integer(1000);

와 비슷하게 만들어져 있다.

두번째 결과값은 JVM이 메모리를 아끼기 위해 발생된다.  -128 에서 127사이의 범위를 가진 int 일때  2의 시점에서 d를 위한 새로운 reference 가 만들어 지지 않고 이전에 만들어 놓았던 c의 reference에 assign 하기만 만 한다. 

Memory saveing rule 때문이다.

• Boolean
• Byte
• Character from \u0000 to \u007f (7f is 127 in decimal)
• Short and Integer from -128 to 127

자료형을 쓸땐 == 보다는 .equal로 감싸주는 것이 좋다.

Stack<Integer> 로 Integer을 사용했기 때문에 이슈가 발생했다.

평소에는 int 를 쓰기 때문에 경험하지 못했던 것 같다.

 

---

결론적으로 Stack 을 사용한 방법도 ArrayList보다 쬐금 효율적이었다.

Success

Details 

Runtime: 27 ms, faster than 8.54% of Java online submissions for Min Stack.

Memory Usage: 42.7 MB, less than 7.97% of Java online submissions for Min Stack.

 

다른분의 모범답안.

https://leetcode.com/problems/min-stack/discuss/509793/Java-Solution-one-Stack-O(1)-time-solution

Java Solution one Stack O(1) time solution - LeetCode Discuss

class MinStack {
    ListNode top;
    
    public class ListNode{
        int data;
        int min;
        ListNode next;
        
        ListNode(int data) {
            this.data = data;
            next = null;
            min = Integer.MAX_VALUE;
        }
    }
    
    /** initialize your data structure here. */
    public MinStack() {
        top = null;
    }
    
    public void push(int x) {
        ListNode t = new ListNode(x);
        t.next = top;
        if(top == null){
            t.min = t.data; // SecondStack.Push(t.data);
        } else {
            if(t.data < top.min) {
                t.min = t.data; // SecondStack.Push(t.data);
            } else {
                t.min = top.min; // SecondStack.Push(top.min);
            }
        }
        top = t;
    }
    
    public void pop() {
        if(top == null) {
            System.err.println("Empty Stack");
            return;
        }
        top = top.next;
    }
    
    public int top() {
        return top.data;
    }
    
    public int getMin() {
        return top.min;
    }
}

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

 

힘들다..