[ 프로그래머스_Lv2 ] 주식가격 ( 스택 - 자바스크립트 )

문제

https://programmers.co.kr/learn/courses/30/lessons/42584

 

코딩테스트 연습 - 주식가격

 

 

How to Solve ?

 

풀이법 1 -  2중 루프

 

크게 고민 안하고 풀 수 있는 방법이다. 파이썬으로 하면, 시간 상으로도 문제는 없다고 하지만 문제의 의도답게 풀지 않았기에 다른 방법을 찾아봤다.

function solution(prices) {
  const answer = [];
  let stack = [];

  for (let i = 0; i < prices.length; i++) {
    for (let j = i + 1; j < prices.length; j++) {
      if (prices[i] <= prices[j]) {
        stack.push(1);
      }
    }

    answer.push(stack.length);
    stack = [];
  }
  return answer;
}

풀이법 2 -  스택

 

다음 값이 자신 보다 작지 않으면 스택에 담아두며 진행 하다가, 다음 값이 자신보다 큰 경우 !

 

충돌한 값과 스택에 저장 해놓은 모든 값들을 비교하여, 충돌한 값보다 작다면 < 충돌한 값이 인덱스 - 비교된 값의 인덱스 > 를 빼서 정답을 구해주면 된다.

 

충돌없이 끝까지 진행되면 Price의 길이에서 스택에 각각 저장 해놓은 인덱스를 빼주면 된다.

 

이해가 어려울 수 있을 것 같아 사진을 첨부하였다!

남아 있다 == 자신보다 작아진 적이 없다가 성립 하는 이유

 

예를 들어서 [1,2] 가 남았다고 가정해보면, 2보다 작았던 적이 없었기 때문에 2가 스택에서 나가지 않은 것이다. 고로, 2보다 작은 1보다 작았을리는 더더욱 없다 :)

function solution(prices) {
  const stack = [];
  const answer = Array(prices.length).fill(0);

  for (let i = 0; i < prices.length; i++) {
    // 주식 가격이 이전보다 낮음.
    while (stack.length && prices[i] < prices[stack[stack.length - 1]]) {
      // 이전에 저장 해놓은 idx 중 가장 위의 값을 뺸다.
      // 그 이유는, 가장 위 == 가장 뒤에 등장한 녀석.
      let temp = stack.pop();

      // 현재 인덱스 값에서 뺀 인덱스를 값에 넣어 주면
      // 몇 초 동안 유지 됬는지 알 수 있음.
      answer[temp] = i - temp;
    }
    stack.push(i);
  }

  // 남아 있다는건, 자신보다 작아진 경우가 없다는 것.
  // 최대 길이에서 자신의 인덱스를 제외
  while (stack.length) {
    let temp = stack.pop();
    answer[temp] = prices.length - temp - 1;
  }

  console.log(answer);
}