[Java] - 주식가격 (42584) (Stack)

📚 문제 - 42584

초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.

제한사항

• prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
• prices의 길이는 2 이상 100,000 이하입니다.

입출력 예

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

•  입출력 예 #1
  1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다.
  2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다.
  3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다.
  4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다.
  5초 시점의 ₩3은 0초간 가격이 떨어지지 않았습니다.

 

⌨️ 작성한 코드

import java.util.Stack;

class Solution {
    public int[] solution(int[] prices) {
        int[] answer = new int[prices.length];
        Stack<Integer> idxStack = new Stack<>(); // 주가 하락 X 때 인덱스를 저장할 스택

        for (int i = 0; i < prices.length; i++) {
            // 주가 하락 O, answer에 가격이 떨어지지 않은 기간 저장
            while (!idxStack.isEmpty() && prices[i] < prices[idxStack.peek()]) {
                int j = idxStack.pop();
                answer[j] = i - j;
            }
            // 주가 하락 X, 인덱스를 스택에 저장
            idxStack.push(i);
        }

        // 스택에 저장된 인덱스로, 주가 하락 X 때의 가격이 떨어지지 않은 기간 저장
        while (!idxStack.isEmpty()) {
            int j = idxStack.pop();
            answer[j] = prices.length - 1 - j;
        }

        return answer;
    }
}

• 접근방식:
  주가 하락하지 않을 때의 인덱스를 저장할 스택을 생성했다. 주식가격의 배열을 순회하면서 현재 주식가격이 스택에 저장된 인덱스일 때의 가격보다 작으면, 가격이 떨어진 것이므로, 해당 인덱스는 pop()하고 answer에 가격이 떨어지지 않은 기간을 저장한다. 순회 후, 스택이 빌 때까지 가격이 떨어지지 않은 기간을 answer에 저장한다. 마지막에 answer를 retrun 한다.
  
  
• 로직:
  prices가 [1, 2, 3, 2, 3] 면, i가 3일 때 주가가 하락했으므로 j = 2이고 answer [2]는 1이 된다.  

  i	idxStack	answer [] 저장
  0	[0]
  1	[0, 1]
  2	[0, 1, 2]
  3	[0, 1, 3]	answer [2] = 3 - 2 =1
  4	[0, 1, 3, 4]

  순회 후, 스택 [0, 1, 3, 4]를 pop()하며 answer에 가격이 떨어지지 않은 시간을 저장하면 answer [4, 3, 1, 1, 0]가 된다.