155. Min Stack

https://leetcode.com/problems/min-stack/description/?envType=study-plan-v2&envId=top-interview-150

Min Stack - LeetCode

https://github.com/fineman999/algorithm_java/issues/7

155. Min Stack · Issue #7 · fineman999/algorithm_java

---

1. 서론

이번에도 알고리즘과 더불어 다른 것들을 적용하고 싶었지만 해당 문제에서 찾기는 어려웠다. 그래서 이번에는 알고리즘 구현만 있다.

 

2. 알고리즘 분석

최소한의 요소를 일정한 시간 내에 푸시 팝, 상단 및 검색을 지원하는 스택을 설계

• MinStack(): 스택 개체를 초기화
• void push(int val): val를 stack에 push
• void pop(): stack 상단의 요소를 제거
• int top(): stack의 상단의 요소를 조회
• int getMin(): 스택의 최소 요소를 검색
• 각 함수에 대해 O(1) 시간 복잡도를 갖는 솔루션을 구현

Example 1:

Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output
[null,null,null,null,-3,null,0,-2]

Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top();    // return 0
minStack.getMin(); // return -2

3. 알고리즘 풀이

class MinStack {
    private Node now;

    public MinStack() {
    }

    public void push(int x) {
        if (now == null) {
            now = new Node(x, x, null);
        } else {
            now = new Node(x, Math.min(x, now.min), now);
        }

    }

    public void pop() {
        now = now.subNode;
    }

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

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

    private static class Node {
        int val;
        int min;
        Node subNode;

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

Node Class

• 멤버 클래스인 Node 클래스는 static으로 만들었다. 이펙티브 자바에서 아이템 24. 멤버 클래스는 되도록 static으로 만들라.에서 말한 static 멤버 클래스의 장점으로 외부 클래스와 멤버 클래스는 독립적으로 작용할 수 있다. 그렇게 되면 서로간의 결합도를 낮추고 안전하게 사용할 수 있게 된다.
• Node 클래스의 인스턴스 필드 값으로 val(값), min(최소값), subNode(하위 노드)를 추가했다.
• Node 클래스의 생성자로 val, min 그리고 하위 노드를 가르키는 subNode를 받는다. 새로운 Node가 이전 Node를 가지고 있게 구현했다.

MinStack Class

• MinStack 클래스는 생성자를 빈값으로 받게 하였다. - (val, min의 값이 없으면 안됨)
• push를 통해 현재 now가 null일 시 새로운 인스턴스 필드를 추가한다.
• 아닐 시 Math.min를 통해 최소값을 업데이트 하고 새로운 Node로 now를 업데이트 한다.

void pop()

• 현재 노드에서 하위 노드를 가리키게 만든다. stack 처럼 이전 노드를 버리게 된다.

int top()

• 현재 노드의 값을 리턴한다.

int getMin()

• 계속해서 최소값을 업데이트 했던 min을 리턴한다.

3.1 결과

LeetCode 결과