[프로그래머스]stack/queue-주식가격

처음 짠 풀이

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

굳이 스택을 임포트해서 쓸 필요가 있나? 그렇게 하면 스택 하나랑 배열 하나 쓰는 거라 memory 절약 차원에서 그냥 배열 하나로 해결해버림.. 대신 time complexity가 O(n^2)이다.

• 두번째 풀이

import java.util.Stack;

    class Solution {
        public int[] solution(int[] prices) {
            Stack<Integer> beginIdxs = new Stack<>();
            int i=0;
            int[] answer = 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();
                    answer[beginIdx] = i - beginIdx;
                }
                beginIdxs.push(i);
            }
            while (!beginIdxs.empty()) {
                int beginIdx = beginIdxs.pop();
                answer[beginIdx] = i - beginIdx - 1;
            }

            return answer;
        }
    }

솔루션을 보고 직접 짠 풀이! 스택을 이용해 뒤에서부터 시작해서 i번째 요소보다 큰 요소값을 가진 smallest index를 찾으면 된다.