Solution.java

class Solution {
    public int[] solution(int[] prices) {
        int[] answer = {};
        
        answer = new int[prices.length];
        
        answer[answer.length - 1] = 0;
        
        for (int i = prices.length - 2; i >= 0; i--) {
            int j = 1;
            while (i + j < prices.length - 1) {
                if (prices[i] <= prices[i + j]) {
                    j += answer[i + j];
                }
                else {
                    break;
                }
            }
            
            answer[i] = j;
        }
        
        return answer;
    }
}

어떻게 풀면 효율성을 통과할지 감도 안 잡힌다..

다음에 다시 도전해봐야겠다.

---

문득 아이디어가 떠올라 풀었더니 바로 통과되었다.

스택/큐로는 풀지 않았고 DP를 이용하여 풀었다.

역시 DP는 아이디어가 떠오르냐 안오르냐 싸움인듯..

---

질문하기랑 다른 사람의 풀이를 보니 그냥 이중 for문으로도 풀리는듯..

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges