Study
data-structure
coding-test
stack
42584

주식가격 (opens in a new tab)

문제 해결 방법

  • 스택에는 가격이 떨어지지 않은 시점의 index를 저장한다
  • prices 배열을 순회하면서 현재 가격과 스택의 top의 가격을 비교한다
    • 크거나 같다면 -> stack.push()
    • 작다면 -> answer 배열에 index - stack.pop() 값으로 변경
  • prices 배열 순회 후에 스택이 비워져 있지 않다면, 스택 순회
    • answer 배열에 prices.length - (stack.pop() + 1) 값으로 변경

오답노트

  • 스택을 활용해 문제를 해결해야 하는 것은 알았으나, 이를 어떻게 접근할지가 막막했다
  • 결국, 풀이 코드 (opens in a new tab)를 참고해서 풀었다
  • 대신 그림을 그려가면서 코드를 이해하고 내꺼화 하기 위해 노력했다

문제 풀이과정

코드

function solution(prices) {
  const answer = new Array(prices.length).fill(0);
  const stack = [];
 
  for (let i = 0; i < prices.length; i += 1) {
    while (stack.length && prices[i] < prices[stack[stack.length - 1]]) {
      const s = stack.pop();
      answer[s] = i - s;
    }
    stack.push(i);
  }
 
  while (stack.length) {
    const s = stack.pop();
    answer[s] = prices.length - (s + 1);
  }
  return answer;
}

실패했던 코드

  • 기존에 자바스크립트로 스택을 만들어 본 클래스를 활용하고 싶었다
  • 그러나, 테스트 케이스는 통과했지만 효율성 테스트에서 시간 초과가 발생했다
  • 당연한거임.. (그냥 연습해봤다 쳐야지)
class Stack {
  #arr;
 
  constructor(values) {
    this.#arr = values ?? [];
  }
 
  getStack() {
    return this.#arr;
  }
 
  push(el) {
    this.#arr = [...this.#arr, el];
  }
 
  pop() {
    const newArr = [...this.#arr];
    this.#arr = newArr.slice(0, -1);
    return Number(newArr.slice(-1));
  }
 
  get isEmpty() {
    return this.#arr.length === 0;
  }
 
  get top() {
    return this.#arr[this.#arr.length - 1];
  }
 
  get length() {
    return this.#arr.length;
  }
}
 
function solution(prices) {
  const answer = new Array(prices.length).fill(0);
  const stack = new Stack();
 
  for (let i = 0; i < prices.length; i += 1) {
    while (stack.length && prices[i] < prices[stack.top]) {
      const s = stack.pop();
      answer[s] = i - s;
    }
    stack.push(i);
  }
 
  while (stack.length) {
    const s = stack.pop();
    answer[s] = prices.length - (s + 1);
  }
  return answer;
}
42626React Component and Hooks