[프로그래머스 자바] 주식가격 (Lv.2)

 

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

프로그래머스

 

 

import java.util.*;

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

 

문제 보면 스택 써야 풀 수 있다. 

가격 수가 최대 1만이면, 이중 포문 쓰면 1억이 되어서 시간 초과가 될 것 같았다. 

 

또 스택에는 인덱스를 넣도록 했다. 

주식 가격이 떨어지는 시점에서, 현재 가격의 인덱스와 stack 에 있는 인덱스의 차가 곧 시간차 이기 때문. 

 

마지막에 while 문은, prices 가 떨어지지 않은 채로 끝난 경우에는 아직 stack에 남아있기 때문에 이걸 다시 해줘야 한다. 

 

stack에서 나온 해당 인덱스의 answer 배열에 시간차를 대입해주면 끝!