[프로그래머스/LV2] 주식가격(Stack)

문제 설명

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

제한사항

• prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
• prices의 길이는 2 이상 100,000 이하입니다.

입출력 예

prcies	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초간 가격이 떨어지지 않았습니다.

※ 공지 - 2019년 2월 28일 지문이 리뉴얼되었습니다.

값이 떨어지지 않은 주식들을 모아 계산해야하기 때문에

Stack구조가 사용하기 적절하다고 생각하여 Stack구조를 이용해 문제를 풀어보았다.

 

1. 코드

import java.util.*;

class Solution {
    public int[] solution(int[] prices) {
        int[] answer = new int[prices.length];
        Stack<Integer> stack = new Stack<Integer>();
        
        for(int i=0;i<prices.length;i++){
            while(!stack.isEmpty()){
                int peek = stack.peek();
                
                //스택에 있는 값이 더 클경우 값이 떨어진 것이므로
                if(prices[peek]>prices[i]){
                    stack.pop();//스택에서 빼주고
                    answer[peek]=i-peek;//answer에 idx차이만큼 값을 저장해준다.
                }else{
                    break;//값이 안떨어진 경우 다음 i 검사하도록 break
                }
                
            }
            stack.push(i);
        }
        
        //끝까지 가격이 안떨어진 주식들은 stack안에 계속 존재하므로 answer에 값 계산해서 넣어준다.
        while(!stack.isEmpty()){
            int pop = stack.pop();
            answer[pop]=prices.length-(pop+1);
        }
        return answer;
    }
}

 

Stack에 prices배열값을 계속 쌓고 값이 떨어지지 않은 주식의 인덱스값만을 저장해준다.

반복문을 돌려서 스택을 peek한 값과 배열값을 비교하여 peek한 값이 더 클 경우 주식의 값이 떨어진 것이므로,

스택에서 pop하여 꺼내주고 pop한 인덱스와 현재 인덱스의 차이만큼 answer배열에 저장해준다.

중간에 값이 떨어진 주식들은 위와 같은 방법으로 answer배열에 기록해주고,

끝까지 가격이 떨어지지 않은 주식들은 스택에 쌓아놨기때문에 마지막에 반복문을 이용하여 값을 계산하여 answer배열에 기록해준다.