[240326] 알고리즘 리부트 39일차 - 프로그래머스 주식 가격 자바

구하고자 하는 것은 특정일자의 가격을 기준으로 가격이 떨어진 날까지의 기간이므로 그 날짜들을 구분할 수 있는 인덱스를 가지고 활용해야 한다. 따라서 스택에 들어갈 값은 배열의 인덱스이다. 여기서 스택을 활용할 수 있다고 생각하게 되는 지점은 앞으로의 주식 가격이 아닌 이전 주식가격들과 비교해서 기간을 구한다는 점이다. 따라서 현재 주식 가격보다 가장 최근 주식 가격이 더 높다면 해당 가격을 가진 날짜는 하루 동안 떨어지지 않은 것이고 해당 날짜를 스택에서 제거한다.

정답 배열에 값을 넣을 때는 제거될 스택의 값이 더 이상 고려되지 않아도 되는 값이고 구간이 정해지는 값이므로 제거될 스택의 값을 정답 배열의 인덱스로 잡고 현재 넣고자 하는 인덱스와의 차를 구해 기간을 담으면 된다. 그리고 또 다시 가장 최근의 값과 비교했을 때 넣으려는 값이 크다면 스택에 담아주고 직전 값이 더 크다면 그 값도 현재 일자가 되서야 값이 떨어진 것이기 때문에 스택의 인덱스와 현재 인덱스의 차를 구해 정답 배열에 넣어주고 해당 스택의 값은 제거해준다. 

import java.util.*;

class Solution {
    public int[] solution(int[] prices) {
        
        int[] answer = new int[prices.length];
            
        int len = answer.length;
        
        Deque<Integer> stk = new ArrayDeque<>();
        
        for(int i = 0; i < len; i++){
                        
            if(stk.isEmpty() || (!stk.isEmpty() && prices[stk.peek()] <= prices[i])) {                
                stk.push(i);
            }
            else{
                while(!stk.isEmpty() && prices[stk.peek()] > prices[i]) {
                    answer[stk.peek()] = i - stk.pop(); //현재 넣으려고 하는 인덱스와 비교해서 거리를 넣기
                }
                stk.push(i);
            }
        }
        
        if(!stk.isEmpty()) {
            while(!stk.isEmpty()) {
                answer[stk.peek()] = (len-1)-stk.pop();
                }
        }       
        return answer;
    }
}