LV2. 주식가격

문제 설명

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

제한사항

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

입출력 예

입출력 예 설명

• 1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다.
• 2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다.
• 3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다.
• 4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다.
• 5초 시점의 ₩3은 0초간 가격이 떨어지지 않았습니다.

나의 풀이
이중 for문을 통해 값을 하나하나 비교하며 주식 가격이 떨어지는 경우에 다음 가격부터 다시 차례로 비교하는 방식을 사용하면 쉽게 풀 수 있는 문제였다.

하지만 이 문제가 스택/큐를 사용하는 문제였기 때문에, 한 시간 이상 해당 Logic을 고민했던 것 같다.

우선, Stack에는 값이 떨어지지 않은 '초'만 집어넣는다.
1. 0초일 때, 1은 아직 비교할 대상이 없으므로 stack에 0을 push.
2. 1초일 때의 값 2는 0초일때보다 커졌으므로, stack에 1을 push.
3. 2초일 때 값 3도 이전의 값보다 커졌기 때문에 stack에 2를 push
이 때, 이전의 값과 비교만 하면되는 이유는 이전의 값은 그 이전의 값보다 크기 때문에, 이전의 값보다만 크면 당연히 그 전의 값들보다는 크다는 소리다.
현재까지 stack의 값[0,1, 2]
4. 3초일 때 값 2는 이전 값보다 작다.
-> 2초일 때의 가격이 떨어지지 않은 기간이 1초밖에 안된다는 뜻. 따라서 2초일때 해당 원소를 stack에서 pop해주고 해당 값은 (n초)를 뜻하므로, answer에 해당 인덱스에 값을 집어넣는다.
5. 위와 같은 logic을 끝까지 집어넣었다면, stack에 남은 값들을 가지고 계산을 해주면 된다. stack의 최상단부터 시작하여 answer에 집어넣는다.
6. 최상단에 해당하는 '초'가 prices의 길이와 얼마나 차이가 나는지를 구하여 answer의 인덱스가 최상단 '초'에 해당하는 곳에 넣으면 되는데, 이 때, -1을 해주는 이유는 prices의 길이는 예를들어, 5이면 5초이지만, 우리가 구현할 때는 i를 0부터 시작해주어서 0초부터 시작했기 때문이다.

말을 좀 어지럽게 해놓았지만, 코드를 보면 이해가 갈 것이다.

이중for문을 이용한 코드

import java.util.*;

class Solution {
    public int[] solution(int[] prices) {
        int[] answer = {};
        
        answer = new int[prices.length];
        
        for(int i=0;i<prices.length;i++){
            for(int j=i+1;j<prices.length;j++){
                answer[i]++;
                if(prices[i]>prices[j]){
                    break;
                }
            }
        }
       
       	return answer;
    }
}

Stack을 이용한 코드

import java.util.*;

class Solution {
    public int[] solution(int[] prices) {
        int[] answer = {};
        answer = new int[prices.length];
        Stack <Integer> st = new Stack<>();
        
        for (int i = 0; i < prices.length; i++) {
            while (!st.isEmpty() && prices[i] < prices[st.peek()]) {
                answer[st.peek()] = i - st.peek();
                st.pop();  // 답을 구했기 때문에 stack에서 제거
            }
            
            st.push(i); //몇 초인지 stack에 push한다.
        }

        while (!st.isEmpty()) { //가장 상단의 원소부터 계산. 가장 상단의 원소는 마지막 원소, 전체 길이 -1 에서 그 원소의 값을 빼면, 떨어지지 않은 기간을 구할 수 있다.
            answer[st.peek()] = prices.length - st.peek() - 1;
            st.pop();
        }
        return answer;
    }
}