[JavaScript] 주식가격 - 스택/큐

프로그래머스 알고리즘 고득점 Kit - 스택/큐

 

문제설명

n초 간의 주가를 초 단위로 기록한 배열 prices가 매개변수로 주어질 때, 각 초의 주가를 기준으로 해당 초 부터 n초 사이에 가격이 떨어지지 않은 시간은 몇 초인지 배열에 담아 return 하도록 solution 함수를 완성하세요.

 

제한사항

prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
prices의 길이 n은 2 이상 100,000 이하입니다. (2 <= n <= 100,000)

 

입출력 예

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

 

입출력 예 설명

1초의 주가는 1이며 1초부터 5초까지 총 4초간 주가를 유지했습니다.
2초의 주가는 2이며 2초부터 5초까지 총 3초간 주가를 유지했습니다.
3초의 주가는 3이며 4초의 주가는 2로 주가가 떨어졌지만 3초에서 4초가 되기 직전까지의 1초간 주가가 유지 된것으로 봅니다. 따라서 5초까지 총 1초간 주가를 유지했습니다.
4초의 주가는 2이며 4초부터 5초까지 총 1초간 주가를 유지했습니다.
5초의 주가는 3이며 5초 이후로는 데이터가 없으므로 총 0초간 주가를 유지했습니다.

 

 

---

 

문제 풀이

function solution(prices) {
  const answer = Array(prices.length).fill(0); // 결과를 저장할 배열
  const stack = []; // 가격과 인덱스를 저장할 스택

  for (let i = 0; i < prices.length; i++) {
    // 현재 가격보다 스택의 가격이 높으면 가격이 떨어진 것이므로 스택에서 꺼냄
    while (stack.length > 0 && stack[stack.length - 1][0] > prices[i]) {
      const [_, index] = stack.pop();
      answer[index] = i - index; // 가격이 유지된 기간 계산
    }
    // 현재 가격과 인덱스를 스택에 저장
    stack.push([prices[i], i]);
  }

  // 스택에 남아 있는 요소는 끝까지 가격이 떨어지지 않은 경우
  while (stack.length > 0) {
    const [_, index] = stack.pop();
    answer[index] = prices.length - 1 - index;
  }

  return answer;
}

 

동작 원리

1. 결과 배열 초기화:

• answer 배열은 가격이 떨어지지 않은 기간을 저장합니다.
• 초기값을 0으로 설정합니다.
  

const answer = Array(prices.length).fill(0);

 

 

2. 스택 활용:

• stack은 현재 확인 중인 가격과 인덱스를 저장합니다.
• 가격이 감소하는 시점을 빠르게 찾기 위해 사용합니다.

3. 현재 가격 비교:

• 스택의 마지막 요소와 현재 가격을 비교합니다.
• 가격이 떨어진 경우, 해당 가격의 유지 기간을 계산하고 결과 배열에 저장합니다.

while (stack.length > 0 && stack[stack.length - 1][0] > prices[i]) { 
    const [price, index] = stack.pop(); 
    answer[index] = i - index; 
}

 

 

4. 스택에 현재 가격 추가:

• 현재 가격과 인덱스를 스택에 저장합니다.
• 스택은 가격이 "감소하지 않은 순서"로 유지됩니다.

stack.push([prices[i], i]);

 

 

5. 스택 처리:

• 스택에 남아 있는 가격은 끝까지 가격이 떨어지지 않은 경우입니다.
• 유지 기간을 prices.length - 1 - index로 계산합니다.

while (stack.length > 0) { 
    const [_, index] = stack.pop(); 
    answer[index] = prices.length - 1 - index; 
}