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

https://school.programmers.co.kr/learn/courses/30/lessons/42584

프로그래머스

문제를 이해하는데 시간이 오래 걸려 질문 게시판을 참고해서 이 문제를 이해했습니다. 문제 설명에서 애매한 부분이 있었는데 추가 설명을 하자면 특정 시간에서의 주식 가격이 자신의 가격보다 크거나 같은 시점을 유지하다 처음으로 내려가는 시점까지의 그 시간을 구하는 것이 이 문제의 핵심입니다. 다시 말해 주식 가격이 자기 자신보다 처음으로 내려 가는 시점 이후에는 주식 가격이 오르든 내리든 상관이 없습니다.

그리고 prices의 인덱스 하나를 순차적으로 돌 때마다 1초의 시간이 걸린다고 생각해야 합니다.

🔍  고찰 과정

스택 자료구조를 활용하여 시간 정보를 계산하였습니다. 계산하는 과정은 다음과 같습니다.

1️⃣ prices의 인덱스 정보를 담는 스택을 하나 만든다.
2️⃣ prices 배열을 for문을 활용하여 하나씩 살핀다.
3️⃣ prices의 인덱스를 스택에 쌓아가며 주가가 내려가는 시점이 오면 스택에 있는 인덱스를 꺼내어 시간을 계산해준다.
4️⃣ prices 배열을 전부 돌았는데도 스택에 인덱스 값이 남아 있다면 주가가 내려간 시점이 없다는 의미이므로 그에 맞는 시간 계산을 해준다.

 

---

✏️ 코드

import java.util.Stack;

class Solution {
    public int[] solution(int[] prices) {
        int pLen = prices.length;
        int[] answer = new int[pLen];
        Stack<Integer> stack = new Stack<>(); // prices의 인덱스를 담을 스택
        
        for (int idx = 0; idx < pLen; ++idx) {
            
            while (!stack.isEmpty() && prices[stack.peek()] > prices[idx]) {
                int sIdx = stack.pop();
                answer[sIdx] = idx - sIdx; // 시간 계산해주기
            }
            
            stack.push(idx);
        }
        
        while (!stack.isEmpty()) { // 나머지 시간 계산해주기
            int idx = stack.pop();
            
            answer[idx] = pLen - 1 - idx;
        }
        
        return answer;
    }
}