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

문제

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

풀이

처음에 이중 for문으로 풀었는데 답도 틀리고 효율성도 틀렸다.
풀이를 찾아보다가 stack으로 풀어야 한다는 것을 알았다.

스택으로 풀어야 하는 이유

1. 스택이 비어있으면 현재 주식 가격의 index를 stack에 쌓는다.
2. 스택이 비어있지 않으면 현재 주식가격(prices[i])과 stack의 가장 상단의 주식가격(prices[stack.peek()])을 비교한다.
3. 만약 stack의 가장 상단의 주식가격(prices[stack.peek()])이 현재 주식가격(prices[i])보다 크다면 stack 안에 있는 값들을 하나씩 뺴면서 stack의 주식 가격을 정답 배열(answer)에 넣는다. 현재 stack에 남아 있는 값들은 모두 현재 주식가격보다 크다는 말이므로 stack이 비워질 때 까지 한다.
   [예시]
   answer[stack.peek()](현재 스택의 index의 정답 배열) = i(현재 index) - stack.peek()(현재 스택의 index)
4. 만약 위에 해당이 안되면 현재 주식가격보다 stack 가장 상단의 주식가격이 더 작다는 뜻이므로 stack에 그대로 쌓아주면 된다.

코드

import java.util.*;

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

        for (int i = 0; i < prices.length - 1; i++) {
        	// 현재 주식가격보다 stack 가장 상단의 주식가격이 더 크면 stack이 비워질 때 까지 
            // 정답배열에 현재 index에서 해당 stack의 값 index를 뺀 값을 넣어준다.
            while (!stack.isEmpty() && prices[i] < prices[stack.peek()]) {
                answer[stack.peek()] = i - stack.peek();
                stack.pop();
            }
            
            // 위에 해당이 안되면 현재 주식가격보다 stack 가장 상단의 주식가격이 더 작다는 뜻이므로 stack에 그냥 쌓아준다.
            stack.push(i);
        }

		// 위에서 처리되지 않은 stack에 남아있는 값은 주식가격의 길이에서 자신의 index값을 뺴주고 1을 더 빼준다.
        // 1을 더 빼주는 이유는 자기자신의 index 값은 빼줘야 하기 떄문이다.
        for (int x : stack) {
            answer[x] = prices.length - x - 1;
        }

        return answer;
    }
}