[Java] 프로그래머스 - 주식가격

각 시점의 가격이 처음으로 떨어질 때까지 걸린 시간을 구하는 문제.

 

1. 문제 유형

스택, 배열, 구현

 

2. 내가 놓친 포인트

처음 떠올린 접근 : 현재 가격과 바로 직전 가격만 비교하면서, 가격이 떨어지면 스택에서 하나 꺼내 처리하려고 했다.

오답 원인: 이 문제는 가격값 자체보다 각 시점(인덱스) 기준으로 답을 구해야 하는데, 처음엔 값 중심으로 생각했다. 또한 현재 가격이 들어왔을 때 이전 시점 하나만 처리하는 걸로 생각했는데 실제로는 여러 인덱스가 연속으로 답이 확정될 수 있다. 마지막까지 스택에 남아 있는 인덱스들은 끝까지 가격이 떨어지지 않은 경우라는 점도 처음엔 헷갈렸다.

 

 

3. 핵심 로직 & 해결 방법

핵심 조건: 스택에는 가격이 아니라 인덱스를 저장한다.

풀이 아이디어:

1. 배열을 왼쪽부터 순회하면서 현재 인덱스를 확인한다.
2. 현재 가격이 스택 top 인덱스의 가격보다 작다면, 그 인덱스를 꺼내 현재 인덱스 - 꺼낸 인덱스를 answer에 기록한다. 이 과정을 가능한 만큼 반복한다.
3. 현재 인덱스는 아직 답이 정해지지 않았으므로 스택에 넣는다. 순회가 끝난 뒤 스택에 남은 인덱스들은 마지막 인덱스 - 현재 인덱스로 처리한다.

4. 구현 코드

import java.util.*;

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

        for (int i = 0; i < prices.length; i++) {
            while (!stack.isEmpty() && prices[stack.peek()] > prices[i]) {
                int index = stack.pop();
                answer[index] = i - index;
            }
            stack.push(i);
        }

        while (!stack.isEmpty()) {
            int index = stack.pop();
            answer[index] = prices.length - 1 - index;
        }

        return answer;
    }
}

시간 복잡도: O(N) / 공간 복잡도: O(N)

---

 

인사이트

• 이 문제에서는 answer 배열을 채워야 하므로 값보다 인덱스 저장이 핵심이었다.
• 마지막까지 남은 스택 처리도 예외가 아니라 문제 로직의 일부로 생각해야 덜 헷갈린다.

 

문제 출처 - https://school.programmers.co.kr/learn/courses/30/lessons/42584