[Stack] Min Stack

155. Min Stack

지문은 링크에서 확인해주세요.

1. 해답을 보지 않고 스스로 문제를 해결한 과정

var MinStack = function() {
  this.arr = [];
  this.minVal = Number.MAX_SAFE_INTEGER;
};

/** 
 * @param {number} val
 * @return {void}
 */
MinStack.prototype.push = function(val) {
  this.arr.push(val);
  this.minVal = Math.min(this.minVal, val);
};

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

  if(this.minVal !== val) {    
    return;
  }

  this.minVal = Number.MAX_SAFE_INTEGER;
    
  for(let i = 0; i < this.arr.length; i++) {
    this.minVal = Math.min(this.minVal, this.arr[i]);
  }
};

/**
 * @return {number}
 */
MinStack.prototype.top = function() {
  return this.arr.at(-1);
};

/**
 * @return {number}
 */
MinStack.prototype.getMin = function() {
  return this.minVal;
};

/** 
 * 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()
 */

본 프로그램 강의에서 설명된 접근법 1) push() / pop() 연산마다 최소값을 비교해서 min 변수에 업데이트하는 방법을 참고하였습니다.

단, pop 메소드는 지문의 요구 조건 You must implement a solution with O(1) time complexity for each function. 을 만족하지 못하였습니다.

2. 여러 해답을 직접 찾아서 자신이 작성한 알고리즘에 대해서 회고한 내용

본 프로그램 강의에서 설명된 접근법 2) stack의 각 요소마다 “값+최솟값”을 저장하는 방법을 참고하였습니다.

function StackNode(val, minVal) {
  this.val = val;
  this.minVal = minVal;
}

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

/** 
 * @param {number} val
 * @return {void}
 */
MinStack.prototype.push = function(val) {
  const topNode = this.arr.at(-1);  
  let newNode = null;

  if(!topNode) {
    newNode = new StackNode(val, val);
  }else {
    const minVal = Math.min(val, topNode.minVal);    
    newNode = new StackNode(val, minVal);  
  }  

  this.arr.push(newNode);  
};

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

/**
 * @return {number}
 */
MinStack.prototype.top = function() {
  return this.arr.at(-1).val;
};

/**
 * @return {number}
 */
MinStack.prototype.getMin = function() {
  return this.arr.at(-1).minVal;
};

필자의 해답과 달리 본 해답은 You must implement a solution with O(1) time complexity for each function. 을 만족하였습니다.