[프로그래머스] 주식 가격 (Java, lv2)

 

문제 출처

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

프로그래머스

 

 

문제 풀이

초 단위로 기록된 주식 가격이 담긴 배열 prices가 주어질때 가격이 떨어지지 않는 기간은 몇초인지 return

- 제한 사항 int[] prices의 길이는 2 이상 100,000 이하 

- O(n^2)으로 풀이시 O(10^10) 발생 가능

- 스택을 사용하여 O(N) 풀이, 인덱스 번호를 스택에 넣는다는 아이디어를 생각하지 못했다.

 

prices : [1, 2, 3, 2, 3]
return : [4, 3, 1, 1, 0]

 

prices[i] < prices[stack.peek()] 인 경우 감소가 발생했으므로

peek idx 값을 꺼내어 answer[idx] = i(현재 위치) - idx 로 갱신해준다

 

 

prices 최대 길이까지 순차 순회 완료하고, stack이 비어있지 않은 경우

하나씩 꺼내서 answer[idx] = 전체 길이 - idx 로 정답을 갱신해준다

 

제출 코드

import java.util.*;

class Solution {
    public int[] solution(int[] prices) {
        int[] answer = new int[prices.length];
        
        Deque<Integer> stack = new ArrayDeque<>();
        
        for(int i = 0; i < prices.length; i++) {
            while(!stack.isEmpty() && prices[i] < prices[stack.peek()]) {
                int idx = stack.pop();
                answer[idx] = i - idx;
            }
            
            stack.push(i);
        }
        
        while(!stack.isEmpty()) {
            int idx = stack.pop();
            answer[idx] = prices.length - idx - 1;
        }
        
        
        return answer;
    }
}