[JAVA] 프로그래머스 - 주식가격

이 문제는 자료구조를 사용하지 않고 2중 for문을 사용해도 통과하는 문제이다.

시간복잡도 상 10,000 * 10,000 이라 빡빡하거나 안될 줄 알았는데 통과가 되는 것 같다.

 

스택의 자료구조를 사용하였다.

인덱스를 스택에 넣고, 해당 인덱스의 값이 스택의 top()보다 작으면 인덱스의 차로 계산을 하고, 현재 top의 계산이 끝나도 스택에 존재하는 모든 top과의 비교를 통해 주식의 하락세를 확인해야한다.

그리고 무조건 모든 인덱스는 스택에 한번씩은 들어가 다음 연산을 수행한다.

 

 

import java.util.*;
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 idx = stack.pop();
                answer[idx] = i - idx;  
            }
            stack.push(i);
        }
        int last = stack.pop();
        while(!stack.isEmpty()){
            int next = stack.pop();
            answer[next] = last - next;
        }
        return answer;
    }
}