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

📌 Problem

주어지는 정수 배열에서 인덱스는 시간을 원소는 주식의 가격을 의미한다. 각 시간별로 주식 가격이 떨어지지 않는 시간을 구하면 된다.

📌 Code

• Stack

class Solution {
    public int[] solution(int[] prices) {
        int[] times = new int[prices.length];

        Stack<Integer> stack = new Stack<>();

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

        while (!stack.isEmpty()) times[stack.peek()] = prices.length - stack.pop() - 1;

        return times;
    }
}

• Queue

class Solution {
    public int[] solution(int[] prices) {
        int[] times = new int[prices.length];

        Queue<Integer> queue = new PriorityQueue<>((a, b) -> {
            if (prices[a] == prices[b]) return a - b;
            else return prices[b] - prices[a];
        });

        for (int time = 0; time < prices.length; time++) {
            while (!queue.isEmpty() && prices[time] < prices[queue.peek()])
                times[queue.peek()] = time - queue.poll();
            queue.offer(time);
        }

        while (!queue.isEmpty()) times[queue.peek()] = prices.length - queue.poll() - 1;

        return times;
    }
}