40분 넘게 고민 고민 하다가 도저히 스택으로 못 풀겠어서 에라 모르겠다 하고 2중 for문 [완전탐색] 으로 풀었는데 효율성이 통과가 되서 놀랐다. 그리고 정답을 찾아보니 해당 문제를 스택으로 푼 사람들이 있어서 아직 갈 길이 멀다고 생각했다.

프로그래머스에서 테스트한 효율성 시간으로 보면 완전탐색이 훨씬 짧게 나오는데 아무래도 효율성 확인할때 배열의 길이가 짧게 나온것 같다. 아마 배열의 길이가 길면 길수록 스택을 사용한 풀이가 압도적으로 시간이 줄어들 것 이다.

어느정도 이렇게 풀어야겠다 라고 생각의 가닥은 잡히는데 거기서 조금 더 구체화를 못시켜서 코드 구현을 못한것 같다. 조금 더 구현 능력을 길러야겠다.

내 풀이

package com.company;

class Solution {
    public int[] solution(int[] prices) {
        //answer 선언
        int[] answer = new int[prices.length];

        //모든 요소에 대해서 완전 탐색 수행 - 2중 for문
        //시작점을 선언
        for (int i = 0; i < prices.length; i++) {
            //시작하는 값
            int startValue = prices[i];
            //count 용 변수
            int count = 0;
            //시작하는 값 다음부터 시작하는 값 과 비교하여 count를 올리고 작은 값이 나오면 break
            for (int j = i + 1; j < prices.length; j++) {
                count++;
                if(prices[j] < startValue)
                    break;
            }
            //answer에 count 삽입
            answer[i] = count;
        }

        return answer;
    }
}

정답 참조

import java.util.Stack;

class Solution {
    public int[] solution(int[] prices) {
        Stack<Integer> beginIdxs = new Stack<>();
        int i=0;
        int[] terms = new int[prices.length];

        beginIdxs.push(i);
        for (i=1; i<prices.length; i++) {
            while (!beginIdxs.empty() && prices[i] < prices[beginIdxs.peek()]) {
                int beginIdx = beginIdxs.pop();
                terms[beginIdx] = i - beginIdx;
            }
            beginIdxs.push(i);
        }
        while (!beginIdxs.empty()) {
            int beginIdx = beginIdxs.pop();
            terms[beginIdx] = i - beginIdx - 1;
        }

        return terms;
    }
}