[Lv.2] 프로그래머스 - 주식가격 : Java

프로그래머스

 

 

 

이해하기

참고한 블로그⬇️

[프로그래머스] 주식가격 - java (Stack 활용)

 

큐가 아닌 스택을 활용해야겠다! 까지는 생각했지만, 막상 구현에서 막혔다.

인덱스를 가지고 풀이하는 방식을 참고하였다.

 

 

첫번째 숫자는 1이고, stack이 비어있으니 인덱스 0을 push한다.

두번째 숫자는 2이고, stack.peek()한 인덱스의 값( = 1 )보다 크기에 가격이 떨어지지 않은 것으로 생각하고 인덱스 1을 push한다.

세번째 숫자는 3이고, stack.peek()한 인덱스의 값( = 2 )보다 크기에 가격이 떨어지지 않은 것으로 생각하고 인덱스 2를 push한다.

 

네번째 숫자는 2이고, stack.peek()한 인덱스의 값( = 3 )보다 작다. 이는 가격이 떨어진 것을 의미한다.

가격이 떨어지지 않은 기간을 세는 것이기 때문에 인덱스 2에 대한 계산이 필요하다.

answer[2]의 값은 현재 인덱스(3)에서 stack.peek()의 값인 2를 빼준 값이다.

 

 

다섯번째 숫자는 3이고, stack.peek()한 인덱스의 값( = 2 )보다 크기에 가격이 떨어지지 않은 것으로 생각하고 인덱스 4를 push한다.

마지막 인덱스에 도달하였고, 이제 stack에 남은 값들에 대한 처리를 해주어야 한다.

 

인덱스 4의 가격이 떨어지지 않은 기간은 0이다.

계산식은 'prices 배열의 길이 - 인덱스(4) - 1'이다.

이 계산식을 각각의 인덱스에 적용시켜주면 답은 아래와 같다.

 

 

문제풀이

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[i] < prices[stack.peek()]) {
                answer[stack.peek()] = i  - stack.peek();
                stack.pop();
            }
            stack.push(i);
        }
        
        while (!stack.isEmpty()) {
            answer[stack.peek()] = prices.length - stack.peek() - 1;
            stack.pop();
        }
        
        return answer;
    }
}