프로그래머스 주식가격

https://school.programmers.co.kr/tryouts/71892/challenges

import java.util.*;
import java.util.stream.Collectors;

class Solution {
    public int[] solution(int[] prices) {
        int[] answer = new int[prices.length];
        Stack<Integer> st = new Stack<>();
        for(int i = 0; i < prices.length; i++){
            while(!st.isEmpty() && prices[i] < prices[st.peek()]){
                int index = st.pop();
                answer[index] = i - index;
            }
            st.push(i);
        }
        
        while(!st.isEmpty()){
            int index = st.pop();
            answer[index] = prices.length - 1 - index;
        }
        
        return answer;
    }
}

문제의 조건은 시간당 가격의 수가 주어질때 O(N) 의 시작 복잡도록 각 해당 가격이 몇 초를 떨어지지않고 이어졌는지 구하는 문제이다.
이 문제를 풀기위한 과정은 다음과 같다.
1. 반목문을 통해서 인덱스를 순회한다.
2. 인덱스를 스택에 차례데로 삽입한다.
2. 스택이 비어있거나 스택의 top 보다 현재 인덱스의 값이 작다면 가격이 감소했으므로 이를

int index = st.pop();
answer[index] = i - index;

스택에 저장된 인덱스를 와 현재 인덱스의 차이를 구해서 감소하지 않은 시작은 구한후에 정답 배열에 저장한다.

3. 이후 남은 숫자들은 마지막까지 떨어지지 않은 것 이므로 마지막 인덱스와 차이를 구한후 정답 배열에 저장한다.