12. 프로그래머스 - 주식 가격 (스택)

문제 설명

초 단위로 기록된 주식 가격이 담긴 배열 prices가 주어질 때, 각 시점의 주식 가격이 얼마나 오래 동안 떨어지지 않았는지를 계산하여 배열로 반환하는 함수를 완성하시오.

---

제한 사항

• prices의 각 원소는 1 이상 10,000 이하의 자연수입니다.
• prices의 길이는 2 이상 100,000 이하입니다.

---

입출력 예

pricesreturn

[1, 2, 3, 2, 3]

[4, 3, 1, 1, 0]

---

입출력 예 설명

• 0초 시점의 가격 1은 끝까지 가격이 떨어지지 않음 → 4초 동안 유지됨
• 1초 시점의 가격 2도 끝까지 떨어지지 않음 → 3초 동안 유지됨
• 2초 시점의 가격 3은 3초 시점에 떨어짐 → 1초 동안 유지됨
• 3초 시점의 가격 2는 4초까지 유지됨 → 1초 동안 유지됨
• 4초 시점의 가격 3은 이후 비교 대상이 없음 → 0초 유지됨

---

핵심 요구사항 요약

• prices[i]는 i초 시점의 주식 가격
• 각 가격이 자신보다 더 낮은 가격을 처음 만날 때까지의 시간을 초 단위로 센다
• 만약 끝까지 떨어지지 않으면 남은 전체 시간(끝까지)을 센다

---

이 문제는 주식 가격이 떨어지지 않는 시간을 계산하는 것이 핵심이다.

배열 prices[i]는 i초 시점의 주식 가격을 의미한다.

• prices = [1, 2, 3, 2, 3]
• 시간 :       0 1  2  3  4

그러므로 각 시점에서 시작해서 언제까지 가격이 떨어지지 않는지를 측정해야 한다.

 

그렇다면 우리가 생각할 수 있는 거는 각 i번째 초에 대해, 그 시점 이후의 시간들 중에서 처음 가격이 떨어지는 시점까지의 시간을 세면 된다. 만약 끝까지 안 떨어지면 전체 남은 시간을 세면 된다.

 

또한 시간 복잡도도 생각해 봐야한다 입력에서 봤듯이 아래와 같은 조건이 있다. 

• prices의 길이는 2 이상 100,000 이하입니다.

따라서 O(N^2)은 시간 초가가 되므로 스택을 이용하면 O(N) 수준으로 최적화할 수도 있다.

 

알고리즘 코드

import java.util.Stack;

class Solution {
    public int[] solution(int[] prices) {
        int[] answer = new int[prices.length];
        Stack<Integer> stk = new Stack<>();
        
        for (int i = 0; i < prices.length; i++) {
        // 가격이 떨어지는 순간이 오면
            while (!stack.isEmpty() && prices[i] < prices[stack.peek()]) {
                int prevIndex = stack.pop();
                answer[prevIndex] = i - prevIndex;
            }
            stack.push(i); // 현재 인덱스를 넣는다
        }

        // 아직 떨어지지 않은 애들 (끝까지 유지됨)
        while (!stack.isEmpty()) {
            int idx = stack.pop();
            answer[idx] = prices.length - 1 - idx;
        }	
        
        return answer;
    }
}

 

시간 복잡도 분석

O(N)