문제

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.

기본 지식

스택(Stack)

한 쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO(Last In First Out) 형식의 자료 구조

• pop(): 스택에서 가장 위에 있는 항목을 제거한다.
• push(item): item 하나를 스택의 가장 윗 부분에 추가한다.
• peek(): 스택의 가장 위에 있는 항목을 반환한다.
• isEmpty(): 스택이 비어 있을 때에 true를 반환한다.

풀이

이 문제는 단순하게 노드에 값과 최소값을 동시에 저장하여 스택에 쌓습니다.

Answer :

class MinStack {
    
    class Node{
        int val, min;
        Node(int val, int min){
            this.val = val;
            this.min = min;
        }
    }
    
    Stack<Node> s = new Stack<>();
    
    /** initialize your data structure here. */
    public MinStack() {
        
    }
    
    public void push(int x) {
        Node node = null;
        if(s.isEmpty()){
            node = new Node(x,x);
        }else{
            node = new Node(x, x<s.peek().min ? x : s.peek().min);
        }
        s.push(node);
    }
    
    public void pop() {
        s.pop();
    }
    
    public int top() {
        return s.peek().val;
    }
    
    public int getMin() {
        return s.peek().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();
 */

위 문제를 예시로 설명하겠습니다

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);

위의 순서로 stack에 push했다면, 아래와 같이 stack이 형성될 것입니다.

            val min
top         -3  -3

            0   -2

start       -2  -2 

위와 같은 형식으로 stack에 쌓아두면 가장 위의 노드 min값이 그 stack의 최솟값이 됩니다.

왜냐하면 stack에 최솟값이 push된다면 그것이 pop()이 될 때 까지 또는 새로운 최솟값이 들어오기전까지는 계속 최솟값이 유지 되기 때문입니다.

(이것을 말로 표현하기에는 좀 어려움이 있어 위에 처럼 그림을 그리면서 해보시면 이해가 되실 것으로 예상됩니다.)

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

minStack.pop();

stack에서 pop()으로 가장 위의 노드를 pop합니다.

그러면 그 순간부터는 보시다시피 다시 -2가 최솟값이 될 것입니다.

            val min
top         0   -2

start       -2  -2 

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

조금 더 이해가 쉽게 설명드리자면 저는 최솟값 라인이 생성되는 데 그 라인이 최솟값을 결정한다? 라고 생각합니다. 예를들면

3 5 2 4 1 6 순서로 stack에 push가 되었다고 생각해봅시다 그렇다면 아래와 같은 그림이 형성될 것입니다.

            val min
top         6   1
            1   1
______________________  1이 최솟값이며, 1이 pop()되는 순간 그 밑의 노드의 min값이 최솟값이 될 것이다.          
            4   2
            2   2
______________________  2가 최솟값이며, 2가 pop()되는 순간 그 밑의 노드의 min값이 최솟값이 될 것이다           
            5   3
start       3   3

위에서 말한 바와 같이 새로운 최솟값이 push된다면 새로운 라인(?)이 생성될 것이며, 그 라인(?)의 최솟값이 pop() 된다면 라인(?)이 사라질 것입니다.

출처 : 제가 알고리즘 문제에 막 감을 익히고 있는 단계여서 유튜버 승지니어님의 코드를 인용하였습니다. 도움되는 영상이 많이 있으므로 많은 방문 부탁드리겠습니다.

유튜브 승지니어 해당영상