[Programmers] 고득점 Kit - Stack/Queue : 주식가격 #42584

문제 링크

주식가격

문제 조건

• 가격이 떨어지지 않은 기간이 몇 초인지 return하는 문제입니다.
• prices의 각 가격은 1 ~ 10,000 이하의 자연수입니다.
• prices의 길이는 2 ~ 100,000 이하입니다.

변수 설명

• prices : 초 단위로 기록된 주식가격이 담긴 배열 (매개변수)
• Stock : idx(index)와 price(가격)을 가지는 class
• st : Stock 클래스를 가지는 스택
• len : 매개변수 prices의 길이

코드 설명

[1]

if (st.empty()) {
    st.push(new Stock(i, prices[i]));
    continue;
}

• st이 비어있으면 i와 그 i에 해당하는 prices[i]를 st에 push해줍니다.

[2]

while(!st.isEmpty() && prices[i] < st.peek().price) {
                Stock buffer = st.pop();
                answer[buffer.idx] = i - buffer.idx;
}
st.push(new Stock(i, prices[i]));

• prices[i]가 st top에 있는 price값보다 작다면 그 top.idx에 i - top.idx 값을 넣어줍니다.
• 그 뒤로 st에 push해줍니다.
• 위에 두 작업을 len만큼 수행해줍니다.

[3]

• st에 원소가 없어질 때까지 [2] 작업을 해줍니다.

배운 점

• java.util.EmptyStackException
  • 비어있는 stack에 peek 또는 pop을 하게되면 발생하는 오류
  • stack에서 peek 또는 pop을 하기 전에 비어있는지(empty) 확인해야 합니다.

    문제 해답

import java.util.Stack;

class Stock {
    int idx;
    int price;
    Stock(int idx, int price){
        this.idx = idx;
        this.price = price;
    }
}
class Solution {
    public int[] solution(int[] prices) {
        Stack <Stock> st = new Stack();
        int len = prices.length;
        int[] answer = new int[len];
        for(int i = 0; i < len; i++) {
            if (st.empty()) {
                st.push(new Stock(i, prices[i]));
                continue;
            }
            while(!st.isEmpty() && prices[i] < st.peek().price) {
                Stock buffer = st.pop();
                answer[buffer.idx] = i - buffer.idx;
            }
            st.push(new Stock(i, prices[i]));
        }
        while(!st.isEmpty()){
            Stock buffer = st.pop();
            answer[buffer.idx] = len - buffer.idx - 1;
        }
        return answer;
    }
}