프로그래머스 - 주식가격

leehyunjon·2022년 9월 5일

프로그래머스

Algorithm

목록 보기

109/162

주식가격 : https://school.programmers.co.kr/learn/courses/30/lessons/42584

Problem

Solve

초마다 각 가격이 떨어지는지 확인하고 떨어졌을때 걸리는 시간을 구해야합니다.

풀이

각 가격이 떨어지지 않는 값을 저장할 int[] answer을 선언합니다.

answer[i]에는 i의 값을 저장합니다.

Stack<Price> stack을 정의하고 가격이 떨어지지 않은 주식을 stack에 저장하게 됩니다.
만약 stack에 있는 주식 가격이 현재 초의 가격보다 높다면 가격이 하락한것이기 때문에 이때까지 가격이 유지된 시간을 answer에 저장해주고 하락한 주식은 stack에서 제거해줍니다.

Price의 idx는 해당 주식 가격의 초를 의미하고, price는 주식 가격을 의미합니다.
answer[i] = i - answer[stack.pop().idx]

모든 시간에 대한 주식을 확인 한뒤, stack에 남아있는 주식가격은 하락하지 않은 주식이 되게 됩니다. 그렇기 때문에 해당 주식 시간을 마지막 시간에서 그 당시의 시간을 빼주어 갱신해줍니다.

answer[i] = end - answer[stack.pop().idx]

Code

import java.util.Stack;
class Solution {
    public int[] solution(int[] prices) {
        int[] answer = new int[prices.length];
        //각 주식의 시간 초기화
        for(int i=0;i<prices.length;i++){
            answer[i] = i;
        }
        
        //하락하지 않은 주식 저장
        Stack<Price> stack = new Stack<>();
        //하락 여부
        boolean[] check = new boolean[prices.length];
        for(int i=0;i<prices.length;i++){
            if(stack.isEmpty()){
                stack.push(new Price(i, prices[i]));
            }else{
            	//해당 시간의 주식보다 하락했다면 stack에서 제거하고 answer를 갱신해줍니다.
                while(!stack.isEmpty() && stack.peek().price > prices[i]){
                    Price p = stack.pop();
                    answer[p.idx] = i - answer[p.idx];
                    check[p.idx] = true;
                }
                //해당 시간의 주식 저장
                stack.push(new Price(i,prices[i]));
            }
        }
        int end = prices.length-1;
        
        //하락하지 않은 주식을 마지막 시간에서 빼준다.
        for(int i=0;i<prices.length;i++){
            if(!check[i]){
                answer[i] = end - answer[i];
            }
        }
        
        return answer;
    }
    
    class Price{
        int idx;
        int price;
        public Price(int idx, int price){
            this.idx = idx;
            this.price = price;
        }
    }
}