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

문제 소개

오늘 풀었던 프로그래머스 - 주식가격 문제를 정리합니다.

이 문제는 언제 가격이 떨어지는지를 초 단위로 측정하여 각 시점마다 가격이 떨어지지 않은 기간을 반환하는 문제입니다.

문제 링크: 주식가격 - 프그래머스

---

문제 접근 방식

이 문제는 다음과 같은 방식으로 접근했습니다:

1. 각 시점의 인덱스를 스택에 저장하면서
   현재 가격이 과거보다 낮아지는 순간을 탐지
2. 가격이 하락하면, 해당 시점까지 걸린 시간을 계산해 기록
3. 마지막까지 가격이 떨어지지 않은 항목은
   배열 끝까지 유지된 것으로 처리 (n - 1 - i)

---

해결 과정 및 코드

핵심 아이디어

1. stack에는 가격이 아직 떨어지지 않은 시점의 인덱스를 담음
2. 현재 가격이 더 낮으면, 이전 가격의 유효 시간이 끝난 것 → 현재 인덱스 - 이전 인덱스
3. 끝까지 유지된 항목은 배열 끝 - 현재 위치

코드

시간 복잡도 : O(N)

import java.util.*;

class Solution {
    public int[] solution(int[] prices) {
        int n = prices.length;
        int[] answer = new int[n];
        ArrayDeque<Integer> stack = new ArrayDeque<>();

        for (int i = 0; i < n; i++) {
            // 가격이 떨어지는 시점 발견
            while (!stack.isEmpty() && prices[i] < prices[stack.peek()]) {
                int idx = stack.pop();
                answer[idx] = i - idx;
            }
            stack.push(i);
        }

        // 끝까지 가격이 떨어지지 않은 경우 처리
        while (!stack.isEmpty()) {
            int idx = stack.pop();
            answer[idx] = n - 1 - idx;
        }

        return answer;
    }
}

단순 구현으로 해결할 경우(O(N²))

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