1. 주식가격

하나의 주식이 오르고 내린다. 오르고 내린 가격들이 적혀있다. 이때 각 시간대별로 떨어지지않은 구간이 몇초인지 리턴하면 된다.(언제나 예시를 보면서 알아보자!)

     prices	         return
[1, 2, 3, 2, 3]	[4, 3, 1, 1, 0]

0초일때 1$ 하던 주식은 끝까지 떨어지지 않으므로 4초간 유지된다고 할 수 있다.
1초일떄 2$ 하던 주식은 3초간
2초일때 3$ 하던 주식은 1초간
3초일때 2$ 하던 주식은 1초간
4초일때 3$ 하던 주식은 0초간 유지된다. 그러므로 위와 같은 시간 분포도가 리턴된다.

그럼 코드로 구현해보자

2. 접근 방법

내가 짠 코드랑 다른 사람의 코드 두가지를 소개하겠다.

내가 짠 코드는 이중 포문으로 되어있다.

• pseudo code
  • found boolean값을 만든다.(값이 떨어지지 않으면 현재 idx에서 끝 idx를 빼주면 된다)
  • 이중 포문을 만든다
  • 안쪽포문에서 자신보다 작은 값이 있는지 찾는다.
  • 계산해서 answer에 push해준다.

function forLoop(prices) {
  let answer = [];

  let stock;

  let found = false;

  for (let i = 0; i < prices.length; i++) {
    stock = prices[i];
    found = false;
    for (var j = i + 1; j < prices.length; j++) {
      if (stock > prices[j]) {
        answer.push(j - i);
        found = true;
        break;
      }
    }
    if (!found) answer.push(j - i - 1);
  }
  return answer;
}

이번에는 스택 자료구조를 써보겠다. 이때 stack에는 pricesIdx를 저장하고 나중에 그 idx에 맞게 answer에 값을 입력하면 된다.

• pseudo code
  • prices를 순회하면서 떨어진 가격이 검색중
    • 발견되면 바로 계산해서 answer에 원하는 위치에 입력
    • 아니면 idx를 stack에 입력
  • stack에 따라서 answer에 계산해서 입력함

function stack(prices) {
  let answer = Array(prices.length).fill(0);

  let pricesIdx = [];
  let length = prices.length;

  for (let i = 0; i < length; i++) {
    while (
      pricesIdx.length &&
      prices[i] < prices[pricesIdx[pricesIdx.length - 1]]
    ) {
      let loweredPricesIdx = pricesIdx.pop();
      answer[loweredPricesIdx] = i - loweredPricesIdx;
    }
    pricesIdx.push(i);
  }
  while (pricesIdx.length) {
    let temp = pricesIdx.pop();
    answer[temp] = length - temp - 1;
  }
  return answer;
}

주식가격 끝!