[Programmers / Level 2] 42584. 주식가격 (Java)

💡 Info

• 난이도: Lv2
  프로그래머스 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42584
  풀이 링크(GitHub): hayannn/CodingTest_Java/프로그래머스/2/주식가격

입출력 조건

입출력 예시

문제 이해

• 주식 가격을 1초 단위로 변화를 배열로 만든다음 -> 가격이 하락하지 않은 기간을 배열로 반환하면 되는 문제

알고리즘

풀이 시간 : 35분

• 가격이 떨어질 때까지 stack에 인덱스 저장
• 가격이 떨어지는 순간 -> stack에서 이전 인덱스를 꺼내 현재 인덱스와의 차이 계산
• 끝까지 남아 있는 stack의 요소들은 끝까지 가격이 유지된 경우이니 n - index - 1로 처리

import java.util.*;

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

        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 - idx - 1;
        }
        
        return answer;
    }
}

결과