[JavaScript] 155. Min Stack

오늘 라이브코딩을 했는데, 알고리즘 구현을 요구하는 문제가 아닌 좀 창의적인 문제 해결을 원하는 문제였다.

개인적으로 참신한 발상이 맘에 들어 포스팅한다.

---

Problem

Min stack 문제는 단순히 Stack클래스를 구현하면 된다.
다만, 새로운 메서드가 추가되는데 getMin() 을 Constant time에 구현해야 한다.

Initial Approach

처음에는 생각한 방법은 다음과 같다.
min변수를 설정하여 push되는 값마다 갱신해주려고 했으나, pop하면 min값을 처음부터 다시 찾아야한다.
그래서 min, secondMin 두 변수를 저장하면 어떨까? 했으나 이것도 결국 두 변수가 pop되면 다시 찾아야하는 점이 여전히 문제로 남게된다.

Solution

그래서 보완한 최종로직은 다음과 같다.
스택에 push했을 때 저장하는 형태를 객체로 다음과 같은 저장한다.

{
  value: "현재 push된 데이터",
  min: "스택의 최소값과 현재 데이터 중 더 작은 값"
}
  

min을 저장할 때 스택의 마지막 인덱스의 min과 비교하여 저장한다.
그러면 항상 stack의 가장 마지막 인덱스의 min값이 스택전체의 min값이 된다.

이 후에 들어오는 데이터에 상관없이 나와 내 이전데이터만 의존하게 된다.
그렇기 때문에, 어떤 값이 pop되든 영향을 받지 않게 된다.
그러므로 min을 얻기 위해서 단순히 가장 마지막 데이터의 min값을 참조하면 된다.

space를 조금 더 사용하는 대신, sorting해야하는 시간을 보완하는 컨셉이다.

전체 코드는 다음과 같다.

var MinStack = function() {
    this.stack=[];
};

/** 
 * @param {number} val
 * @return {void}
 */
MinStack.prototype.push = function(val) {
    this.stack.push({
        value: val,
        min : this.stack.length ? Math.min(val,this.getMin()) : val
    })
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function() {
    return this.stack.pop();
};

/**
 * @return {number}
 */
MinStack.prototype.top = function() {
    return this.stack[this.stack.length-1].value;
};

/**
 * @return {number}
 */
MinStack.prototype.getMin = function() {
    return this.stack[this.stack.length-1].min;
};

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

---

이렇게 데이터에 데이터와 관련된 정보를 추가하는 형태는 Queue에서 많이 사용했다.
BFS에서 최단거리를 찾을 때 사용하는 queue에서 해당 데이터가 얼마만큼 거리가 있는지 함께 저장하고, 현재 최단거리보다 큰 데이터가 들어오면 바로 continue하는 로직을 주로 구현했다.

stack을 이용한 문제는 많이 풀어보지 못했고, queue에서는 자연스럽게 사용했을 법한 형태를 생각못했다는게 아쉬웠다.ㅠㅠ

다음에는 맞출수있기를!