[코딩테스트] Java 주식가격

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.

포인트

시간 복잡도 O(N^2)으로 잘 관리하면 문제가 패스하는 것을 확인했습니다. 하지만 시간복잡도를 줄이고 싶어 Stack을 이용하였고, O(N)의 시간 복잡도를 갖는 코드를 구현하였습니다.

소스코드

import java.util.*;

class Solution {
    public int[] solution(int[] prices) {
        int len = prices.length;
        int[] ans = new int[len];
        Stack<Integer> stack = new Stack<>();
        
        // 각 시간의 인덱스를 스택에 저장
        for (int i = 0; i < len; i++) {
            // 현재 가격이 스택의 마지막 가격보다 낮으면, 하락 시간 계산
            while (!stack.isEmpty() && prices[i] < prices[stack.peek()]) {
                int idx = stack.pop();
                ans[idx] = i - idx; // 하락 시간 계산
            }
            stack.push(i); // 현재 인덱스를 스택에 추가
        }
        
        // 남아 있는 인덱스들은 끝까지 가격이 떨어지지 않음
        while (!stack.isEmpty()) {
            int idx = stack.pop();
            ans[idx] = len - 1 - idx;
        }
        
        return ans;
    }
}

코드 설명

• 루프를 통해 각 시점의 가격을 순회합니다.
  • 스택의 크기와 현재 가격이 마지막 주식 가격보다 낮으면
    • 스택에서 해당 인덱스를 꺼내고, 그 하락 시간을 i - idx로 계산하여 ans 배열에 저장.
  • 현재 시점 i를 스택에 추가하여 이후 가격 변화에 대해 추적.
• 스택에 남아있는 시점들은 가격이 떨어지지 않은 것이므로 전체 크기에 대해 배열에 저장합니다.