프로그래머스: 주식가격

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

프로그래머스

설명

주식 배열을 0번째부터 확인한다.

• 증가한다면? stack에 주식(prices[i])와 넣는 시간(i)을 저장한다.
• 감소한다면? stack에서 값을 peek 해서 떨어졌는지 확인한다.
  • 떨어졌다면? stack에서 pop하고 answer 배열에 해당 주식의 index에 (현재 시간 -  주식을 기록한 시간)을 저장한다. 

가장 마지막에는 stack이 빌 때까지 값을 꺼내면서 answer 배열을 완성한다. 

 

코드

import java.util.*;

class Solution {
    static Stack<int[]> stack;
    public int[] solution(int[] prices) {
        int[] answer = new int[prices.length];
        stack = new Stack<>();
        
        int before = prices[0];
        
        stack.add(new int[]{before, 0}); // value와 넣는 시간
        
        for(int i = 1; i < prices.length; i++) {
            int cur = prices[i];
            if(cur < before) {  // 더 작은 값을 만났다.
                while(!stack.isEmpty()) {
                    int[] stock = stack.peek();
                    if(stock[0] > cur) {
                        answer[stock[1]] = i - stock[1];
                        stack.pop();
                    } else break;
                }
            } 
            stack.add(new int[]{cur, i});
            before = cur;
        }
        
        while(!stack.isEmpty()) {
            int[] stock = stack.pop();
            answer[stock[1]] = prices.length - stock[1] - 1;
        }
        
        return answer;
    }
}