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

문제 링크

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

풀이 과정

이중 for문을 돌며 기준 주식 가격을 배열의 뒤 요소들과 각각 비교해 카운트를 증가시키는 방식으로 문제를 풀었습니다.

O(N^2)의 시간 복잡도를 가져 효율성 체크에서 실패할 것으로 생각했지만 예제가 부족했는지 성공을 했고, 이후 카테고리가 스택/큐 인 것을 감안해 자료구조를 이용해 문제를 접근했습니다.

스택은 배열로 이뤄졌습니다. 첫 번째 요소로 가격을, 두 번째 요소로 해당 일자에서 가격이 떨어지지 않은 기간을 갖습니다. 기간(time)은 pop 할 때 계속 누적되므로 이 값으로 answer를 구성합니다.

코드

1. 이중 for 문

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

2. 스택

    public static int[] solution(int[] prices) {
        int[] answer = new int[prices.length];
        Stack<int[]> stack = new Stack<>();
   
        for (int i = prices.length - 2; i >= 0; i--) {
            int time = 0;
   
            while (!stack.isEmpty() && stack.peek()[0] >= prices[i])
                time += stack.pop()[1];
   
            answer[i] = stack.push(new int[]{prices[i], time + 1})[1];
        }
   
        return answer;
    }