[LeetCode] 155. Min Stack

문제 출처: https://leetcode.com/problems/min-stack/

Min Stack - LeetCode

문제

push, pop, top 그리고 최소 원소를 가져오는 기능을 상수 시간에 수행하는 스택을 디자인하라.

 

MinStack 클래스를 구현하라:

• MinStack()은 스택 객체를 초기화한다.
• void push(val)는 스택에 원소 val을 삽입한다.
• void pop()은 스택의 탑 원소를 제거한다.
• int top()은 스택의 탑 원소를 얻는다.
• int getMin()은 스택에서 가장 작은 원소를 얻는다.

예제

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

풀이

구현이 필요한 함수 중 push, pop, top은 일반적인 스택의 기능으로 리스트(혹은 배열)를 이용해서 구현할 수 있다. 이 문제에서 핵심은 getMin()의 기능을 제공하면서 기존의 메서드의 동작을 그대로 유지하는 것이다.

해결 방법은 min 값을 저장하는 스택을 별도로 갖게 하는 것이다. 코드를 통해 살펴보자.

class MinStack {
    main = [];
    min = [];
    size = 0;

    push(val) {
        this.main.push(val);
        if (this.size == 0 || this.min[size-1] > val) {
            this.min.push(val);
        } else {
            this.min.push(this.min[size-1]);
        }
        this.size += 1;
    }

    pop() {
        this.main.pop();
        this.min.pop();
    }

    top() {
        return this.main[this.size-1];
    }

    getMin() {
        return this.min[this.size-1];
    }
}

min스택의 탑에는 언제나 main스택의 최소값이 저장되어 있도록 유지하는 것이 핵심이다. 이를 위해서 다음과 같은 규칙을 따른다.

 

1. main스택에 push가 수행되면 min스택에서도 push가 수행된다.
   • min스택에 push되는 값은 언제나 main 스택의 최소 값이다.
2. main스택에 pop이 수행되면 min스택에서도 pop이 수행된다.

 

push 상황에 대해서 조금 더 살펴보면, 어떤 값 X를 삽입한다고 가정하자.

 

현재 스택에서의 최소 값은 min의 top위치에 저장되어 있을 것이다. 이때 X가 min의 top보다 크다면, 스택의 최솟값은 바뀌지 않을 것이기 때문에 min의 top을 다시 min에 삽입하는 것으로 최소 값을 유지시킬 수 있다. 반대로 X가 더 작다면 min에 X를 삽입하는 것으로 min을 우리가 원하는 상태로 만들 수 있다.

 

Github: 155.js

opwe37/Algorithm-Study