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

🚀링크

https://programmers.co.kr/learn/courses/30/lessons/42584?language=java

💻문제

초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.

제한사항
prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
prices의 길이는 2 이상 100,000 이하입니다.
입출력 예
prices return
[1, 2, 3, 2, 3][4, 3, 1, 1, 0]
입출력 예 설명
1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다.
2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다.
3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다.
4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다.
5초 시점의 ₩3은 0초간 가격이 떨어지지 않았습니다.

🌏문제풀이

1. 문제의 포인트는 stack에 주식가격이 아닌 해당 주식가격의 위치를 담는 것이다. (주식 가격은 중요하지 않고 얼마나 버텼는지가 중요하기 때문)
2. prices[]를 돌면서 마지막 주식가격이 새로 넣을 주식가격보다 낮은 경우 해당 위치를 pop한다. 이때, pop하는 것은 해당 주식가격의 위치임으로 answer[loc] 로 답을 넣어준다.

👩‍💻코드

import java.util.Stack;

class Solution {
    public int[] solution(int[] prices) {
        int[] answer = new int[prices.length];
        Stack<Integer> st = new Stack<Integer>();
        
        for(int i = 0; i<prices.length; i++){
            //stack에는 주식 가격이 아닌 주식가격의 원위치를 담기 때문에
            //비교할 때, prices[st.peek()]과 비교해야함
            while(!st.isEmpty() && prices[st.peek()] > prices[i]){
                int loc = st.pop();
                answer[loc] = i-loc;
            }
            
            st.push(i);
            
        }
        
        while(!st.isEmpty()){
            int l = st.pop();
            //prices.length는 i보다 1만큼 크기 때문에 이를 맞추기 위해 -1
            answer[l] = prices.length - l -1;
        }
        
        return answer;
    }
}