[프로그래머스][스택/큐][JAVA] 주식가격

[프로그래머스][스택/큐][JAVA] 주식가격 스택으로 풀기

programmers.co.kr/learn/courses/30/lessons/42584

코딩테스트 연습 - 주식가격

 

순회를 하면서 자신보다 뒷쪽에 자신보다 더 작은값의 위치가 어디인지만 알면된다.

따라서 뒤에서부터 순회하면서 앞의값보다 작은 값들의 위치를 스택에 쌓아 기억하는 것이 핵심이다.

 

맨 마지막 숫자의 답은 무조건 0이니 그 전 숫자부터 순회한다.

순회를 하면서 다음과 같이 액션해주면 된다.

• "다음 숫자가 나보다 작네?"
  • 현재 인덱스의 답(answer[i])을 1로 설정하고 스택에는 다음 숫자와 그 인덱스 [prices[i+1], i+1] 를 저장한다.
• "다음 숫자가 나보다 같거나 크네?"
  • 스택을 확인한다.
    •  "스택 사이즈가 0이네?"
      • 현재 인덱스의 값은 배열 끝까지 자기보다 작은 수가 없는 것이므로 현재 인덱스부터 배열끝까지의 길이인 것이다.
        즉, answer[i] = length - 1 - i
    • "스택 사이즈가 0보다 크네?
      • 스택 마지막 아이템의 숫자값이 현재 숫자값보다 크거나 같은건 다 지워준다.
      • 다 지운 후에 스택이 없어지면 위에 처럼 answer[i] = length - 1 - i 로 값을 내주면 된다.
      • 다 지웠는데 아직 스택에 값이 남아있다면, answer[i]는 스택 마지막 아이템의 인덱스값과 현재 인덱스의 차이인 stack.peek()[1] - i 가 된다.
        즉, answer[i] = stack.peek()[1] - i 

 

 

import java.util.Stack;
class Solution {
    public int[] solution(int[] prices) {
        int length = prices.length;
        int[] answer = new int[length];
        Stack<int[]> stack = new Stack<>();
        
        answer[length-1] = 0;
        
        for(int i= length-2; i>=0; i--){
            if(prices[i] <= prices[i+1]){
                
                while(stack.size() > 0 && stack.peek()[0] >= prices[i]){
                    stack.pop();
                }
                
                if(stack.size() == 0){
                    answer[i] = length - i - 1;
                } else {
                    answer[i] = stack.peek()[1] - i;
                }
                
            } else {
                answer[i] = 1;
                stack.push(new int[] {prices[i+1], i+1});
            }
        }
        return answer;
    }
}