[JAVA] 스택 : 주식가격

1. 문제 내용

요약
가격 배열이 입력됐을 때 자기자신보다 낮은 가격이 나올 때 까지의 값을 측정

2. 접근 방법
 자기 자신의 높은 값이 나오면 해당 인덱스를 저장하고 낮은값이 나오면 저장한 값들의 역순으로 비교하여 시간을 측정하면 해결될 것으로 보인다 이에 적합한 방식으로 생각되는 스택으로 구현해 보았다

3. 구현과정

입력된 길이만큼 스택에 저장하고 비교하는 과정 

for(int i = 0; i < prices.length; i++){
    while (!stack.isEmpty() && prices[stack.peek()] > prices[i]){
        int index = stack.pop();
        answer[index] = i - index;
    }
    stack.push(i);
}

비교를 전부 하고나서 스택에 남은 값들 처리

while (!stack.isEmpty()){
    int index = stack.pop();
    answer[index] = prices.length - 1 - index;
}

4. 결과
 문제를 푸는 과정에서 시간이 오래걸리는 문제가 발생했었는데 원인으로 생각되는 부분은 완성하는 과정에서 값을 스택에 추가하는 과정을 할 때 마다 스택 내부의 count를 전부 더해주면서 시간복잡도가 N^2에 가깝게 나오게 되었다.
그래서 다른 방식으로 접근해 보았는데 스택에는 index를 저장하고 해당 index를 비교과정에 사용해 낮은 값이 나왔을 때 현재대상의 index와 스택의 index의 차이를 계산해 저장해보았더니 해결되었다 


전체 코드

import java.util.Stack;

class Solution {
    public int[] solution(int[] prices) {
        int[] answer = new int[prices.length];
        Stack<Integer> stack = new Stack<>();


        for(int i = 0; i < prices.length; i++){
            while (!stack.isEmpty() && prices[stack.peek()] > prices[i]){
                int index = stack.pop();
                answer[index] = i - index;
            }
            stack.push(i);
        }

        while (!stack.isEmpty()){
            int index = stack.pop();
            answer[index] = prices.length - 1 - index;
        }

        return answer;
    }
}